算法008——四数之和

四数之和（点击跳转）

在完成 四数之和 之前，一定要先知道三数之和和两数之和是怎样的思想，可以看我前两篇博客三数之和、
两数之和

先对数组排序

在三数之和中，我们是依次固定一个数 i ，在剩下的区间内找到 两数之和 为 -i 的两个数

那么在四数之和当中，我们也可以先依次固定一个数，我们将这个数存放到 a 中，在剩下的区间内找三数之和为target - a 的三个数，此时问题又回到了 三数之和

在剩下的区间内，我们依次固定一个数，将它存放到 b 中，在剩下的区间内找到 两数之和为 target - a - b 的两个数

当我们找到了一组数据时，即两数之和相加等于 target - a - b，此时不要停，缩小范围，继续找，将这组数据存储下来后，让 left++，right–

接下来让我们思考怎样去重，在 三数之和 当中，去重的情况有两种，一是当 left 或者 right 遇到重复元素时，需要跳过此元素，二是在 固定的数 遇到重复元素时需要跳过

然而四数之和，我们固定了两个数，就多了一种情况，所以共有三种情况，如下

1. 当 left 与 right 遇到重复元素
2. 当 b 遇到重复元素
3. 当 a 遇到重复元素
   

代码如下：

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        //排序
        Arrays.sort(nums);
        int n = nums.length - 1;
        for(int a = 0;a <= n;){
            for(int b = a + 1;b <= n;){
                int left = b + 1;
                int right = n;
                //会溢出，用long
                long aim = (long)target - nums[a] - nums[b];
                while(left < right){
                    int sum = nums[left] + nums[right];
                    if(sum > aim){
                        right--;
                    }else if(sum < aim){
                        left++;
                    }else{
                        ret.add(Arrays.asList(nums[a],nums[b],nums[left],nums[right]));
                        //找到后，不停，缩小范围继续找
                        left++;
                        right--;
                        //对 left 与 right 进行去重，注意不要越界
                        while(left < right && nums[left] == nums[left - 1]){
                            left++;
                        }
                        while(left < right && nums[right] == nums[right + 1]){
                            right--;
                        }
                    }
                }
                //对 b 进行去重，不能越界
                b++;
                while(b <= n && nums[b] == nums[b - 1]){
                    b++;
                }
            }
            //对 a 进行去重，不能越界
            a++;
            while(a <= n && nums[a] == nums[a - 1]){
                a++;
            }
        }
        return ret;
    }
}

因为溢出，还以为之前的代码写错了