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
30
31
32
33
34
35
36
//C++ Solution
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> results;
std::sort(nums.begin(), nums.end());
for(int i = 0;i<nums.size();i++) {
int target = -nums[i];
int start = i+1;
int end = nums.size()-1;
while(start<end) {
int sum = nums[start]+nums[end];
if(target<sum) {
end--;
}
else if(target>sum) {
start ++;
}
else {
vector<int> temp(3,0);
temp[0] = nums[i];
temp[1] = nums[start];
temp[2] = nums[end];
results.push_back(temp);
while(start<end && nums[start]==temp[1]) {
start++;
}
while(start<end && nums[end]==temp[2]) {
end--;
}
}
}
while(i<nums.size()-1 && nums[i+1]==nums[i]) {
i++;
}
}
return results;
}
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;
}