去重是这道题的关键！
LeetCode链接：15. 三数之和
LeetCode链接：18. 四数之和
题目1：三数之和
1.题目描述
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
1
2
3
4
5
6
7
8
| 输入：nums =
输出：
解释：
nums + nums + nums = (-1) + 0 + 1 = 0 。
nums + nums + nums = 0 + 1 + (-1) = 0 。
nums + nums + nums = (-1) + 2 + (-1) = 0 。
不同的三元组是 和 。
注意，输出的顺序和三元组的顺序并不重要。
|
示例 2：
1
2
3
| 输入：nums =
输出：
解释：唯一可能的三元组和不为 0 。
|
示例 3：
1
2
3
| 输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
|
提示：
3 <= nums.length <= 3000- $-10^5 <= nums[i] <= 10^5$
2.题解
2.1 双指针
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
| class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> resultList = new ArrayList<>();
int n = nums.length;
for (int first = 0; first < n - 2; first++) {
if (nums[first] > 0) break;
if (first > 0 && nums[first] == nums[first - 1]) continue;
int second = first + 1, third = n - 1;
while (second < third) {
int sum = nums[first] + nums[second] + nums[third];
if (sum == 0) {
List<Integer> list = new ArrayList<>();
list.add(nums[first]);
list.add(nums[second]);
list.add(nums[third]);
resultList.add(list);
while (second < third && nums[second] == nums[second + 1]) second++;
while (second < third && nums[third] == nums[third - 1]) third--;
second++;
third--;
} else if (sum > 0) {
third--;
} else {
second++;
}
}
}
return resultList;
}
}
|
题目2：四数之和
1.题目描述
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c 和 d 互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1：
1
2
| 输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
|
示例 2：
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$
2.题解
2.1 双指针
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
| class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> resultList = new ArrayList<>();
int n = nums.length;
for (int first = 0; first < n - 3; first++) {
if (first > 0 && nums[first] == nums[first - 1]) continue;
for (int second = first + 1; second < n - 2; second++) {
if (second > first + 1 && nums[second] == nums[second - 1]) continue;
int third = second + 1;
int fourth = n - 1;
while (third < fourth) {
long sum = (long) nums[first] + nums[second] + nums[third] + nums[fourth];
if (sum == target) {
List<Integer> list = new ArrayList<>();
list.add(nums[first]);
list.add(nums[second]);
list.add(nums[third]);
list.add(nums[fourth]);
resultList.add(list);
while (third < fourth && nums[third] == nums[third + 1]) third++;
while (third < fourth && nums[fourth] == nums[fourth - 1]) fourth--;
third++;
fourth--;
} else if (sum > target) {
fourth--;
} else {
third++;
}
}
}
}
return resultList;
}
}
|
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
| class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> resultList = new ArrayList<>();
int n = nums.length;
for (int first = 0; first < n - 3; first++) {
if(nums[first] > target && nums[first] >0) break;
if (first > 0 && nums[first] == nums[first - 1]) continue;
for (int second = first + 1; second < n - 2; second++) {
if (nums[first] + nums[second] > target && nums[first] + nums[second] >= 0) break;
if (second > first + 1 && nums[second] == nums[second - 1]) continue;
int third = second + 1;
int fourth = n - 1;
while (third < fourth) {
long sum = (long) nums[first] + nums[second] + nums[third] + nums[fourth];
if (sum == target) {
resultList.add(Arrays.asList(nums[first], nums[second], nums[third], nums[fourth]));
while (third < fourth && nums[third] == nums[third + 1]) third++;
while (third < fourth && nums[fourth] == nums[fourth - 1]) fourth--;
third++;
fourth--;
} else if (sum > target) {
fourth--;
} else {
third++;
}
}
}
}
return resultList;
}
}
|