15. 3Sum

Posted on Edited on

题目

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;
}