15. 3Sum

题目

Given an array S of n integers, are there elements a, b, c in S 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.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

思路

为了避免重复的情况,数组需要先排序一下。

固定一个数字,然后再用两个指针,依次遍历整个数组(类似于two sum),找出符合条件的三个数字。

比如排好序以后的数字是 a b c d e f, 那么第一次固定a, 在剩下的 b c d e f 中进行2sum, 完了以后第二次枚举b, 只需要在 c d e f 中进行2sum,这样就避免了重复。

代码

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
//C++ Solution
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> result;
for(int i = 0;i<nums.size();i++) {
while(i>0 && (nums[i]==nums[i-1])) {
++i;
}
int l = i + 1;
int h = nums.size() -1;
while(l<h) {
int sum = nums[i] + nums[l] + nums[h];
if(sum == 0) {
result.push_back({nums[i] , nums[l] , nums[h]});
while (nums[l]==nums[l+1]) ++l;
while (nums[h]==nums[h-1]) --h;
++l;
--h;
}
else if(sum > 0) {
--h;
}
else {
++l;
}
}
}
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
//Java Solution
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> results = new LinkedList<>();

for(int i=0;i<nums.length;i++) {
int start = i+1;
int end = nums.length-1;

while(start<end) {
if(-nums[i]<nums[start]+nums[end]) {
end--;
}
else if(-nums[i]>nums[start]+nums[end]) {
start++;
}
else {
results.add(Arrays.asList(nums[i], nums[start], nums[end]));
while(start<end && nums[start] == nums[start+1]) {
start++;
}
while(start<end && nums[end] == nums[end-1]) {
end--;
}
start++;
end--;
}
}
while(i<nums.length-1 && nums[i+1]==nums[i]) {
i++;
}
}
return results;
}
Donate comment here