目录

一、 题目<两数之和> easy

1. 解题思路

1）暴力解题法

2）两遍哈希表

3）一遍哈希表

二、题目《三数之和》medium

1. 解题思路（排序+双指针）

三、题目《四数之和》medium

1.解题思路（排序+双指针）

---

一、 题目<两数之和> easy

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

假设每种输入只会对应一个答案。但是，不能重复利用这个数组中同样的元素。

1. 解题思路

遍历数组元素，对于每一个元素A，寻找数组中是否含有另一个元素B使得A+B=目标值，第一个元素A肯定是需要遍历整个数组的，寻找第二个元素B的方式将决定算法的效率，如果需要一种更有效的方法来检查数组中是否存在目标元素。保持数组中的每个元素与其索引相互对应的最好方法是什么？哈希表。

1）暴力解题法

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[] { i, j };
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

空间复杂度；时间复杂度，所以暴力解题法虽然理解简单，但是运行时间最高，所以不可取；

2）两遍哈希表

一个简单的实现使用了两次迭代。在第一次迭代中，我们将每个元素的值和它的索引添加到表中。然后，在第二次迭代中，我们将检查每个元素所对应的目标元素（target - nums[i]target−nums[i]）是否存在于表中。注意，该目标元素不能是 nums[i] 本身！

class Solution {
    public int[] twoSum(int[] nums, int target) {
        //首先将数组中的元素存储于map集合中
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(complement) != i) {
                return new int[] { i, map.get(complement) };
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

时间复杂度：O(n);

空间复杂度：O(n);

时间复杂度和空间复杂度是一个矛盾体。

3）一遍哈希表

事实证明，我们可以一次完成。在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(map.containsKey(target-nums[i]))
            {
                return new int[]{map.get(target-nums[i]), i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

二、题目《三数之和》medium

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

本题的难点在于如何去除重复解；

1. 解题思路（排序+双指针）

算法流程：

1）特判，对于数组长度 n，如果数组为 null或者数组长度小于 3，返回 []。

2）对数组进行排序。

3）遍历排序后数组：

• 对于任意i，若nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于0，直接返回结果。
• 对于重复元素：跳过，避免出现重复解；
• 令左指针 L=i+1，右指针 R=n−1，当 L<R 时，执行循环：
• 当 nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R移到下一位置，寻找新的解；若和大于0，说明 nums[R] 太大，R 左移；若和小于 0，说明 nums[L]太小，L 右移；

复杂度分析

时间复杂度：

数组排序 ，遍历数组 ，双指针遍历

空间复杂度：

import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;

public class test {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>>list1=new ArrayList<>();
        if(nums==null || nums.length<3)
        {
            return list1;
        }

        Arrays.sort(nums);

        for(int i=0;i<nums.length-2;i++)
        {
            if(nums[i]>0)
                return list1;
            if(i>0&& nums[i]==nums[i-1])    //算法中最核心的地方，思考清楚为什么能够消除重复解
                continue;           
            int L=i+1;
            int R=nums.length-1;
            while(L<R)
            {
                if(nums[i]+nums[L]+nums[R]==0)
                {
                    List<Integer>list2=new ArrayList<>();
                    list2.add(nums[i]);
                    list2.add(nums[L]);
                    list2.add(nums[R]);
                    list1.add(list2);
                    while(L<R && nums[L]==nums[L+1])
                        L++;
                    while(L<R && nums[R]==nums[R-1])
                        R--;
                    L++;
                    R--;
                }
                else if(nums[i]+nums[L]+nums[R]>0)
                    R--;
                else
                    L++;

            }
        }
        return list1;
    }

    public static void main(String[] args)
    {
        test test1=new test();
        int[] nums=new int[]{-1, 0, 1, 2, -1, -4};
        System.out.println(test1.threeSum(nums));
    }
}

三、题目《四数之和》medium

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：答案中不可以包含重复的四元组。

1.解题思路（排序+双指针）

固定两个数，然后通过双指针寻找剩下的两个数；

import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;

class Solution 
{
    public List<List<Integer>> fourSum(int[] nums, int target) 
    {
        int length=nums.length;

        List<List<Integer>> result=new ArrayList<>();
        if(nums==null || length<4)
            return result;

        Arrays.sort(nums);

        for(int i=0;i<length-3;i++)
        {
            if(i>0 && nums[i]==nums[i-1])
                continue;

            int min_1=nums[i]+nums[i+1]+nums[i+2]+nums[i+3];
            if(min_1>target)
                break;

            int max_1=nums[i]+nums[length-1]+nums[length-2]+nums[length-3];
            if(max_1<target)
                continue;

            for(int j=i+1;j<length-2;j++)
            {
                if(j>i+1 && nums[j]==nums[j-1])
                    continue;

                int min_2=nums[i]+nums[j]+nums[j+1]+nums[j+2];
                if(min_1>target)
                    break;

                int max_2=nums[i]+nums[j]+nums[length-1]+nums[length-2];
                if(max_2<target)
                    continue;

                int L=j+1;
                int R=length-1;
                while(L<R)
                {
                    if(nums[i]+nums[j]+nums[L]+nums[R]==target)
                    {
                        /*List<Integer>list=new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[L]);
                        list.add(nums[R]);
                        result.add(list);*/
                        result.add(Arrays.asList(nums[i],nums[j],nums[L],nums[R]));
                        while(L<R && nums[L]==nums[L+1])
                            L++;
                        while(L<R && nums[R]==nums[R-1])
                            R--;
                        L++;
                        R--;                        
                    }
                    else if(nums[i]+nums[j]+nums[L]+nums[R]<target)
                        L++;
                    else
                        R--;                    
                }
            }


        }
        return result;

    }
}