【LeetCode】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]]
1
2

示例 2：

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

提示：

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

解题思路：

相信大家前面都做过三数之和，那么本题的思路，可以参考三数之和来做，使用双指针。

可以参考一下 三数之和 做个对比，有什么相同点和什么不同点。

因为要用到双指针，所以排序是必须要做的。

还有就是三数之和，四数之和。。。n 数之和等等，本质都是一样的，这次给大家写一个 n数之和，大家可以直接背下，以后再也不怕 n 数之和了。

具体代码：

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        if (nums.length < 4) {
            return new LinkedList<>();
        }
        return nSum(nums, target, 4, 0);
    }

    // 递归参数：nums，当前目标值target，当前数值的个数n，当前数值的起始索引start
    // 返回n数和的列表，即n元组
    List<List<Integer>> nSum(int[] nums, long target, int n, int start) {
        // 递归的每层都要新建res来传递列表
        List<List<Integer>> res = new ArrayList<>();
        // 递归的终止层：2数之和
        if (n == 2) {
            int left = start, right = nums.length - 1;
            while (left < right) {
                // 剪枝：根据剩下选择闭区间[left, right]里的最小值和最大值剪枝
                // 如果由当前left，left+1组成的最小值比target大的话，剩下的left和right就更大了
                // 因此直接跳出，遍历i+1
                int nMin = nums[left] + nums[left + 1];
                if (nMin > target) {
                    break;
                }
                // 与nMin同理
                int nMax = nums[right] + nums[right - 1];
                if (nMax < target) {
                    break;
                }
                long sum = nums[left] + nums[right];
                if (sum == target) {
                    List<Integer> row = new LinkedList<>();
                    row.add(nums[left]);
                    row.add(nums[right]);
                    res.add(row);
                    // 去重2：去除最后两个值的重复
                    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]) ;
                }
            }
        } 
        // 正常递归层：
        else {
            for (int i = start; i <= nums.length - n; i++) {
                // 去重1：去除当前值的重复。当前值和历史值对比，i-1执行过
                // 注意，去重若放在代码块前面，就是用if continue 以及i-1和i的形式，
                // 若放在后面，就是while i++ 以及 i和i+1的形式
                if (i > start && nums[i - 1] == nums[i]) {
                    continue;
                }
                // sub接住递归回来的结果
                List<List<Integer>> sub = nSum(nums, target - nums[i], n - 1, i + 1);
                // // 后序归来后在当前层的操作：res添加sub和当前值
                for (List<Integer> row : sub) {
                    row.add(nums[i]);
                    res.add(row);
                }
                // 当前值和历史值对比，放在代码块后面，用i和i+1，因为i执行过
                // while (i <= len - n - 1 && nums[i] == nums[i + 1]) {
                //     i++;
                // }
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71