Leetcode/java/18.4-sum.java at master · widmonstertony/Leetcode · GitHub

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
 * @lc app=leetcode id=18 lang=java
 *
 * [18] 4Sum
 */

// @lc code=start
class Solution {
    // kSum解法
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        return kSum(nums, target, 0, 4);
    }
    private List<List<Integer>> kSum(int[] nums, int target, int start, int k) {
        List<List<Integer>> resList = new ArrayList<>();
        if (start == nums.length) {
            return resList;
        }
        // 优化，如果k个当前最小的数都比target大，或者如果k个当前最大的数都比target小
        // 说明当前数组不可能组成target，直接返回空
        if (nums[start] * k > target || target > nums[nums.length - 1] * k) {
            return resList;
        }
        if (k == 2) {
            return twoSum(nums, target, start);
        }
        for (int i = start; i < nums.length; i++) {
            // 如果当前数字和前一位一样，跳过，去重
            if (i != start && nums[i - 1] == nums[i]) {
                continue;
            }
            int currNum = nums[i];
            // 把从下一个数字开始，所有可以组合成target减去当前数字的k-1个答案全部拿到
            List<List<Integer>> onelessKlist = kSum(nums, target - currNum, i + 1, k - 1);
            // 把这些答案里都加上当前数字，并且给到最后答案
            for (List<Integer> eachList : onelessKlist) {
                List<Integer> currResList = new ArrayList<>();
                currResList.add(currNum);
                currResList.addAll(eachList);
                resList.add(currResList);
            }
        }
        return resList;
    }
    private List<List<Integer>> twoSum(int[] nums, int target, int start) {
        List<List<Integer>> resList = new ArrayList<>();
        int left = start, right = nums.length - 1;
        while (left < right) {
            int currSum = nums[left] + nums[right];
            // 如果当前总和小于target，移动左指针
            // 或者如果左边和它之前的一样，跳过，去重
            if (currSum < target || (left > start && nums[left] == nums[left - 1])) {
                left++;
            }
            // 如果当前总和大于target，移动右指针
            // 同时如果右边和它之后的一样，跳过，去重
            else if (currSum > target || (right < nums.length - 1 && nums[right] == nums[right + 1])) {
                right--;
            }
            else {
                resList.add(Arrays.asList(nums[left], nums[right]));
                left++;
                right--;
            }
        }
        return resList;
    }
    // public List<List<Integer>> fourSum(int[] nums, int target) {
    //     Arrays.sort(nums);
    //     List<List<Integer>> resList = new ArrayList<>();
    //     for (int i = 0; i < nums.length; i++) {
    //         // 记得去重
    //         if (i > 0 && nums[i] == nums[i - 1]) {
    //             continue;
    //         }
    //         else {
    //             findThreeSum(nums, i, target-nums[i], resList);
    //         }
    //     }
    //     return resList;
    // }
    // private void findThreeSum(int[] nums, int start, int target, List<List<Integer>> resList) {
    //     for (int i = start + 1; i < nums.length; i++) {
    //         // 记得去重
    //         if (i > start + 1 && nums[i] == nums[i - 1]) {
    //             continue;
    //         }
    //         else {
    //             findTwoSum(nums, i, target - nums[i], resList, start);
    //         }
    //     }
    // }
    // private void findTwoSum(int[] nums, int start, int target, List<List<Integer>> resList, int preStart) {
    //     // 双指针，一个从start开始往后，一个从末尾开始往前
    //     int left = start + 1, right = nums.length - 1;
    //     while (left < right) {
    //         int currSum = nums[left] + nums[right];
    //         if (currSum == target) {
    //             // 保存答案
    //             List<Integer> currList = new ArrayList<>();
    //             currList.add(nums[start]);
    //             currList.add(nums[left]);
    //             currList.add(nums[right]);
    //             currList.add(nums[preStart]);
    //             resList.add(currList);
    //             left++;
    //             right--;
    //             // 记得去重，同时不能超过对方的位置
    //             while (nums[left] == nums[left - 1] && left < right) {
    //                 left++;
    //             }
    //             while (nums[right] == nums[right + 1] && right > left) {
    //                 right--;
    //             }
    //         }
    //         else if (currSum < target) {
    //             left++;
    //         }
    //         else {
    //             right--;
    //         }
    //     }
    // }
}
// @lc code=end