卖萌的弱渣

I am stupid, I am hungry.

Three Sum

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.

Example

For example, given array S = {-1 0 1 2 -1 -4}, A solution set is:

(-1, 0, 1) (-1, -1, 2)

Note

Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)

The solution set must not contain duplicate triplets.

Solution

  • Time: O(N2), Space O(N)
1
2
3
4
5
6
7
8

S = {-1 0 1 2 -1 -4}
排序后：
S = {-4 -1 -1 0 1 2}
      ↑  ↑        ↑
      i  j        k
         →        ←
i每轮只走一步，j和k根据S[i]+S[j]+S[k]=ans和0的关系进行移动，且j只向后走（即S[j]只增大），k只向前走（即S[k]只减小）
如果ans>0说明S[k]过大，k向前移；如果ans<0说明S[j]过小，j向后移；ans==0即为所求。
  • 注：当找到一组解时，需要移动i,j到下一个非重复位置
(Three-Sum.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
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class Solution:
    """
    @param numbersbers : Give an array numbersbers of n integer
    @return : Find all unique triplets in the array which gives the sum of zero.
    """
    def threeSum(self, numbers):
        # write your code here
        result = []
        if len(numbers) < 3:
            return result

        sorted_array = sorted(numbers)
        # a[i] is the first one
        # a[j] is the middle one
        # a[k] is the last one
        for i in range(len(sorted_array)):
            j = i+1
            k = len(sorted_array)-1

            while j<k:
                if sorted_array[i] + sorted_array[k] + sorted_array[j] > 0:
                    k -= 1
                elif sorted_array[i] + sorted_array[k] + sorted_array[j] < 0:
                    j += 1
                else:
                    # found the target
                    # if not duplicated, append it.
                    if [sorted_array[i], sorted_array[j], sorted_array[k]] not in result:
                        result.append([sorted_array[i], sorted_array[j], sorted_array[k]])
                    # move j to next unduplicated pos
                    if sorted_array[j] != sorted_array[j+1]:
                        j += 1
                    else:
                        while j < len(sorted_array)-1 and sorted_array[j] == sorted_array[j+1]:
                            j += 1
                    # move k to next unduplicated pos
                    if sorted_array[k] != sorted_array[k-1]:
                        k -= 1
                    else:
                        while k > 0 and sorted_array[k] == sorted_array[k-1]:
                            k -= 1
        return result