友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
15. 3Sum
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
解题分析
为什么参考资料中，JS 的代码可以通过，但是转成 Java 之后就不能通过呢？
-
一刷
-
二刷
-
二刷（万能方法）
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
// TODO 还没有通过
/**
* TODO 还没有通过
*
* @author D瓜哥 · https://www.diguage.com
* @since 2018-07-19
*/
public static List<List<Integer>> threeSum(int[] nums) {
if (Objects.isNull(nums) || nums.length < 3) {
return Collections.emptyList();
}
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
if (nums[0] * nums[nums.length - 1] > 0) {
return result;
}
for (int i = 0; i < nums.length - 2 && nums[i] <= 0; ) {
int left = i + 1, right = nums.length - 1;
while (left < right && nums[i] * nums[right] <= 0) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
}
if (sum > 0) {
while (left < right && nums[right] == nums[--right]) {}
} else {
while (left < right && nums[left] == nums[++left]) {}
}
}
while (i < nums.length - 1 && nums[i] == nums[++i]) {}
}
return result;
}
public static List<List<Integer>> threeSum2(int[] nums) {
if (nums.length < 3) {
return new ArrayList<>();
}
Set<List<Integer>> result = new HashSet<>();
Arrays.sort(nums);
Map<Integer, Integer> numMap = new HashMap<>(nums.length * 4 / 3 + 1);
for (int i = 0; i < nums.length; i++) {
numMap.put(nums[i], i);
}
if (numMap.size() == 1 && numMap.keySet().contains(0)) {
result.add(Arrays.asList(0, 0, 0));
return new ArrayList<>(result);
}
for (int i = 0; i < nums.length; i++) {
for (int j = nums.length - 1; j > i; j--) {
int minuend = 0 - (nums[i] + nums[j]);
if (numMap.containsKey(minuend)) {
Integer k = numMap.get(minuend);
if (i != k && j != k) {
int[] oneResult = new int[]{nums[i], nums[j], minuend};
Arrays.sort(oneResult);
result.add(Arrays.stream(oneResult).boxed().collect(Collectors.toList()));
}
}
}
}
return new ArrayList<>(result);
}
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
/**
* 双指针
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-08-15 16:08:08
*/
public List<List<Integer>> threeSum(int[] nums) {
if (nums == null || nums.length < 3) {
return Collections.emptyList();
}
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i - 1] == nums[i]) {
continue;
}
int l = i + 1, r = nums.length - 1;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
if (sum < 0) {
while (l < r && nums[l] == nums[++l]) ;
} else if (0 < sum) {
while (l < r && nums[r] == nums[--r]) ;
} else {
result.add(Arrays.asList(nums[i], nums[l], nums[r]));
while (l < r && nums[l] == nums[++l]) ;
while (l < r && nums[r] == nums[--r]) ;
}
}
}
return result;
}
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
/**
* 双指针
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-08-15 16:08:08
*/
public List<List<Integer>> threeSum(int[] nums) {
if (nums == null || nums.length < 3) {
return Collections.emptyList();
}
Arrays.sort(nums);
return numSum(nums, 0, 3, 0);
}
private List<List<Integer>> numSum(int[] nums, int idx, int cnt, int target) {
// 剩余长度不够，则直接返回
if (nums.length - idx < cnt || cnt < 2) {
return new ArrayList<>();
}
List<List<Integer>> result = new ArrayList<>();
if (cnt == 2) {
int l = idx;
int r = nums.length - 1;
while (l < r) {
int sum = nums[l] + nums[r];
int left = nums[l];
int right = nums[r];
if (sum < target) {
while (l < r && nums[l] == left) {
l++;
}
} else if (target < sum) {
while (l < r && nums[r] == right) {
r--;
}
} else {
result.add(new ArrayList<>(Arrays.asList(left, right)));
while (l < r && nums[l] == left) {
l++;
}
while (l < r && nums[r] == right) {
r--;
}
}
}
} else {
for (int i = idx; i < nums.length; i++) {
int num = nums[i];
List<List<Integer>> temp = numSum(nums, i + 1, cnt - 1, target - num);
for (List<Integer> rs : temp) {
rs.addFirst(num);
result.add(rs);
}
while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
i++;
}
}
}
return result;
}