18. 四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + 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 = [], target = 0
输出：[]

提示：

• 0 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

思路

第15题15. 三数之和使用双指针。第一层循环确定 num[i]，然后在剩余数组中找到符合条件的 num[left] 和 num[right]。四数相加也可以借助相同的思路，先借助双层循环确定 num[i] 和 num[j]，然后在剩余数组中寻找符合条件的 num[left] 和 num[right]，只不过 3Sum 是寻找和为 0 的组合，而 4Sum 变为和为任意值的。这里要注意 int 类型边界问题。

public List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums.length < 4) {
        return result;
    }
    Arrays.sort(nums);
    // 最小值大于 0 且比 target 大，注意负数相加会变小
    if (nums[0] > 0 && nums[0] > target) {
        return result;
    }

    int left = 0, right = nums.length - 1;
    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;
            }
            left = j + 1;
            right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum > target) {
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    if (left > j + 1 && nums[left] == nums[left - 1]) {
                        left++;
                        continue;
                    }
                    if (right < nums.length - 1 && nums[right] == nums[right + 1]) {
                        right--;
                        continue;
                    }
                    result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                    left++;
                    right--;
                }
            }
        }
    }
    return result;
}