刷刷刷Day7| 18. 四数之和

18. 四数之和

LeetCode题目要求

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。

示例

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

解题思路

大致过程如下图：

思想类似三数之和的处理，关键在于指针的移动以及可能出现重复的处理。详细内容可以参看代码的说明

上代码

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        // 先排序，便于后续的指针移动及和相加、去重处理
        Arrays.sort(nums);
        
        int len = nums.length;

        // 第一层循环，指针为 i
        for (int i = 0; i < len; i++) {
            // 如果 i 指针的值大于 0 并且 大于 target，由于数组排序，不能出现和为 target， 所以这里直接就返回结果
            if (nums[i] > 0 && nums[i] > target) {
                return res;
            }

            // 去重处理，当前指针的值与前一次的相等，那么就不再处理，直接进入下一次循环
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }

            // 第二层循环，指针为 j
            for (int j = i + 1; j < len; j++) {
                // 去重处理，当前指针的值与前一次的相等，那么就不再处理，直接进入下一次循环
                if (j > i + 1 && nums[j] == nums[j-1]) {
                    continue;
                }

                // 移动的 left 指针，使用 j + 1
                int left = j + 1;
                // 移动的 right 指针，使用 len - 1
                int right = len - 1;

                // 迭代移动
                while (left < right) {
                    // i、j、left、right 四个指针的值相加
                    int c = nums[i] + nums[j] + nums[left] + nums[right];
                    // 如果和 > 目标值，那么移动 right，向左收缩操作，也就是让 right 指针的值小
                    if (c > target) {
                        right--;
                    } else if (c < target) {
                        // 这里是和 < 目标值，那么移动 left，向右收缩操作，也就是让 left 指针的值变大
                        left++;
                    } else {
                        // 如果相等，直接放入结果集
                        res.add(Arrays.asList(nums[i], nums[j], 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--;

                        // 这里在去重后再移动 left、 right 指针，供下一次循环使用
                        left++;
                        right--;
                    }
                }
            }
        }

        return res;
    }
}

重难点

去重，在第一层循环，第二层循环，及找到结果集时都需要做去重处理，否则结果可能就有问题了

附：学习资料链接