18. 四数之和

给你一个由 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

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

示例 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

排序+双指针-long避免溢出-跳过重复数字

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums); // 对数组进行排序，方便后续处理
        List<List<Integer>> ans = new ArrayList<>(); // 存储结果的列表
        int n = nums.length; // 数组长度
        
        for (int a = 0; a < n - 3; a++) { // 第一个数的枚举范围
            long x = nums[a]; // 当前第一个数。注意是long，不然下面的求和会溢出
            if (a > 0 && x == nums[a - 1]) continue; // 如果当前第一个数与前一个数相同，跳过，避免重复
            if (x + nums[a + 1] + nums[a + 2] + nums[a + 3] > target) break; // 优化一：如果当前四个数之和已经大于目标值，说明当前值太大，直接跳出循环
            if (x + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue; // 优化二：如果当前数与数组中最后三个数之和小于目标值，说明当前值太小，需要跳过当前循环
            
            for (int b = a + 1; b < n - 2; b++) { // 第二个数的枚举范围
                long y = nums[b]; // 当前第二个数。注意是long
                if (b > a + 1 && y == nums[b - 1]) continue; // 如果当前第二个数与前一个数相同，跳过，避免重复。题目要求四个数不重复。
                if (x + y + nums[b + 1] + nums[b + 2] > target) break; // 优化一：如果当前四个数之和已经大于目标值，跳出循环
                if (x + y + nums[n - 2] + nums[n - 1] < target) continue; // 优化二：如果当前两数与数组中最后两个数之和小于目标值，跳过当前循环
                
                int c = b + 1, d = n - 1; // 初始化双指针，分别指向第三个数和第四个数
                while (c < d) { // 双指针遍历数组，找出第三个数和第四个数
                    long s = x + y + nums[c] + nums[d]; // 当前四数之和。注意是long
                    if (s > target) d--; // 如果和大于目标值，减小第四个数的值
                    else if (s < target) c++; // 如果和小于目标值，增大第三个数的值
                    else { // 如果和等于目标值
                        ans.add(List.of((int) x, (int) y, nums[c], nums[d])); // 将当前四个数加入结果列表
                        for (c++; c < d && nums[c] == nums[c - 1]; c++) ; // 跳过重复数字。Good
                        for (d--; d > c && nums[d] == nums[d + 1]; d--) ; // 跳过重复数字
                    }
                }
            }
        }
        return ans; // 返回结果列表
    }
}

• 时间复杂度： $O\left(n^3\right)$ ，其中 $n$ 是数组的长度。排序的时间复杂度是 $O(n \log n)$ ，枚举四元组的时间复杂度是 $O\left(n^3\right)$ ，因此总时间复杂度为 $O\left(n^3+n \log n\right)=O\left(n^3\right)$ 。
• 空间复杂度： $O(\log n)$ ，其中 $n$ 是数组的长度。空间复杂度主要取决于排序额外使用的空间。此外排序修改了输入数组 nums，实际情况中不一定允许，因此也可以看成使用了一个额外的数组存储了数组 nums 的副本并排序，空间复杂度为 $O(n)$ 。