18.四数之和

题目:四数之和

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

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按任意顺序返回答案 。

• 示例 1：

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

• 示例 2：

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

• 提示：

1 <= nums.length <= 200
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

思路

先固定两个数i,然后对另外两个数使用双指针,找到两个数之和等于-nums[i]。
再手动去重,把结果四元组存放进ArrayList,返回ArrayList。

• 时间复杂度:O(n³)
• 空间复杂度:O(n)

代码

public List<List<Integer>> fourSum(int[] nums, int target) { // 总时间复杂度O(n³)
    List<List<Integer>> list = new ArrayList<>(); // 空间复杂度:O(n)
    if (nums == null || nums.length < 4) {
        return new ArrayList<>();
    }
    Arrays.sort(nums); // 时间复杂度O(nlog₂n)
    // -2,-1,0,0,1,2
    for (int i = 0; i < nums.length - 3; i++) { // 时间复杂度O(n³)
        // 获取当前最小值，如果最小值比目标值大，说明后面越来越大的值根本没戏
        if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
            break;
        }
        // 获取当前最大值，如果最大值比目标值小，说明后面越来越小的值根本没戏，忽略
        if ((long) nums[i] + nums[nums.length - 1] + nums[nums.length - 2] + nums[nums.length - 3] < target) {
            continue;
        }
        // 去掉重复情况
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        for (int j = i + 1; j < nums.length - 2; j++) { // 时间复杂度O(n²)
            // 去掉重复情况
            if (j > i + 1 && nums[j] == nums[j - 1]) {
                continue;
            }
            int left = j + 1;
            int right = nums.length - 1;
            while (left < right) { // 时间复杂度O(n)
                long sum = (long) nums[left] + nums[right] + nums[i] + nums[j];
                if (sum == target) {
                    list.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                    // 当左右指针扫描到与上一个相等的时候,直接跳过
                    while (left < right && nums[left] == nums[++left]) {
                    }
                    while (left < right && nums[right] == nums[--right]) {
                    }
                } else if (sum < target) {
                    // 当左指针扫描到与上一个相等的时候,直接跳过
                    while (left < right && nums[left] == nums[++left]) {
                    }
                } else {
                    // 当右指针扫描到与上一个相等的时候,直接跳过
                    while (left < right && nums[right] == nums[--right]) {
                    }
                }
            }
        }
    }
    return list;
}