四数之和

目录

一：题目链接

二：题目思路

三：代码实现

一：题目链接

        理解题目需要注意，如果两个四元组元素一一对应，则认为两个四元组重复，选择其中一个四元组即可。比如 [ 0 , 1 , 0 ,  2] 和 [ 1  ,  0  ,2, 0 ] ，那么认为这两个四元组是相同的。选择其中一个即可。

二：题目思路

        我i们的思路是 排序 + 固定数字 + 固定数字 + 双指针 来解决。

        首先，将数组排好序后，我们确定一个固定数 a 从 数组起始位置开始 ，另一个固定数 b 从 a 的下一位开始，再定义两个指针 left 和 right ，如图：

        先看固定数 b 和这两个指针，后续思路就是我们之前所讲的 “三数之和” , （务必理解这篇文章后再看下面思路），只不过这里的判断条件改成 nums[left] + nums[right] == target - a - b;并且过程要注意，最外层的固定数 a 也需要去重。所以大致思路也就是 “三数之和” 最外层再套了个 for 循环。

三：代码实现

        //存储结果集
        List<List<Integer>> ret = new ArrayList<>();

        //排序数组
        Arrays.sort(nums);

        int n = nums.length;

        //小优化
        if (n < 4 || (long) nums[0] + nums[1] + nums[2] + nums[3] > target) {
            return ret;
        }

        for (int i = 0; i < n;) { //固定数字 a
            for (int j = i + 1; j < n;) { //固定数字 b

                long sum = (long) target - nums[i] - nums[j];

                int left = j + 1;
                int right = n - 1;

                while (left < right) {
                    if ((long) nums[left] + nums[right] < sum) {
                        left++;
                    } else if ((long) nums[left] + nums[right] > sum) {
                        right--;
                    } else {
                        //添加当前符合条件的四元组
                        ret.add(Arrays.asList(nums[i], nums[j], nums[left],nums[right]));

                        left++;
                        right--;

                        while (left < right && nums[left] == nums[left - 1]) {
                            left++;
                        }

                        while (left < right && nums[right] == nums[right + 1]) {
                            right--;
                        }
                    }
                }

                //去重 j
                j++;
                while (j < n && nums[j] == nums[j - 1]) {
                    j++;
                }

            }

            //去重 i
            i++;
            while (i < n && nums[i] == nums[i - 1]) {
                i++;
            }
        }

        return ret;

        小优化代码解释：如果当前数组元素不够 四个，或者数组最小的四个数加起来都比 target 大，就可以直接返回了。