[LeetCode] 18. 4Sum

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.

Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

Constraints:
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

四数之和。

给你一个由 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
你可以按 任意顺序 返回答案 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/4sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

依然是双指针逼近的思路做，注意以下几点

• 需要对 input 排序
• 需要四个指针 - i, j, low, high
• 每个指针都需要跳过重复元素
• i 最多到 nums.length - 3

复杂度

时间O(n^3)
空间O(n) - output

代码

Java实现 - 可以处理整型溢出的问题（19行）

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length < 4) {
            return res;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < nums.length - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int low = j + 1;
                int hi = nums.length - 1;
                while (low < hi) {
                    long sum = (long) target - nums[i] - nums[j];
                    if (nums[low] + nums[hi] == sum) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[low], nums[hi]));
                        while (low < hi && nums[low] == nums[low + 1]) {
                            low++;
                        }
                        while (low < hi && nums[hi] == nums[hi - 1]) {
                            hi--;
                        }
                        low++;
                        hi--;
                    } else if (nums[low] + nums[hi] < sum) {
                        low++;
                    } else {
                        hi--;
                    }
                }
            }
        }
        return res;
    }
}

JavaScript实现

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    nums = nums.sort((a, b) => a - b);
    const res = [];
    let low, high, sum;
    // corner case
    if (nums.length < 4) return res;

    // normal case
    for (let i = 0; i < nums.length - 3; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        for (let j = i + 1; j < nums.length - 2; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) continue;
            low = j + 1;
            high = nums.length - 1;
            while (low < high) {
                sum = nums[i] + nums[j] + nums[low] + nums[high];
                if (sum === target) {
                    res.push([nums[i], nums[j], nums[low], nums[high]]);
                    while (low < high && nums[low] === nums[low + 1]) low++;
                    while (low < high && nums[high] === nums[high - 1]) high--;
                    low++;
                    high--;
                } else if (sum < target) {
                    low++;
                } else {
                    high--;
                }
            }
        }
    }
    return res;
};