卖萌的弱渣

I am stupid, I am hungry.

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.

Example

Given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:

1
2
3
4

[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution

(3Sum.py) download
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

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        ret = []
        if not nums:
            return ret

        nums = sorted(nums)

        n = len(nums)
        for i in range(n):
            l = i+1
            r = n-1
            while l<r:
                val = nums[i]+nums[l]+nums[r]
                if val == 0:
                    ret.append(sorted([nums[l],nums[i],nums[r]]))
                    # should not break "-2,0,1,1,2"
                    l += 1
                elif val < 0:
                    l += 1
                else:
                    r -= 1
        return [list(t) for t in set(tuple(element) for element in ret)]
  • Java: 注意规避重复元素
(3Sum.java) download
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

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new LinkedList<List<Integer>>();
        if (nums.length == 0)
            return ret;
        //　排序
        Arrays.sort(nums);

        for (int i=0;i<nums.length-2;i++){
            if(i==0 || nums[i] != nums[i-1]){
                int l = i+1;
                int r = nums.length-1;
                while (l<r){
                    int sums = nums[i]+nums[l]+nums[r];
                    if (sums==0){
                        // asList: array->list
                        ret.add(Arrays.asList(nums[i],nums[l],nums[r]));
                        while(l<r && nums[l]==nums[l+1]) l++;
                        while(l<r && nums[r]==nums[r-1]) r--;
                        l++;
                        r--;
                    }
                    else if(sums<0)
                        l ++;
                    else
                        r--;
                }
            }
        }
        return ret;
    }
}