3 Sum

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.

The solution set must not contain duplicate triplets.

Example：

1
2
3
4
5
6
given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路：
1.首先，还是进行排序处理，然后对三个数我们分别做如下处理：
2.第一个数当做基准数，从数组第一个数开始一直向右遍历到倒数第三个数。
3.另外两个数我们每次都只从基准数右边选取，可以将右边部分当做一个新的数组。
4.借助两个变量（类似于指针），分别指向这个新数组最左和最右元素即为剩下要处理的两个数。
5.有了这三个数我们做如下讨论：
6.如果这三个数之和小于0，则左指针加1；大于0则右指针减1；否则，满足条件，把当前三个数加入结果集，两个指针同时向中间移动。
7.两指针相遇，则基准数下所有结果已经遍历完成，基准数加1，继续寻找结果。
8.这里我们所有结果找到了，但是没有处理重复，思路如下：
9.在基准数操作的时候，有这种情况，如果这个基准数和上一个基准数一样，那么，后面的操作就重复了，得到的结果也会重复，所以，在操作之前，需要判断基准数是否和上一个重复，这样可以避免重复。
10.同样在指针操作的时候，如果和指向的上一个数字一样，也会造成重复，所以，也需要进行判断处理。

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def threeSum(self, nums):
        nums.sort()
        res,i = [],0
        for i in range(len(nums)-2):
            if i == 0 or nums[i] != nums[i-1]:
                lp ,rp= i+1 ,len(nums)-1
                while lp < rp:
                    if nums[i]+nums[lp]+nums[rp] < 0:
                        lp += 1
                    elif nums[i]+nums[lp]+nums[rp] > 0:
                        rp -= 1
                    else:
                        res.append([nums[i],nums[lp],nums[rp]])
                        lp += 1
                        rp -= 1
                        while lp < rp and nums[lp] == nums[lp-1]:
                            lp += 1
                        while lp < rp and nums[rp] == nums[rp+1]:
                            rp -= 1
            i += 1
        return res

备注：在判断指针指向重复的时候一定要使用while，不能用if，因为你不清楚是否是连续重复，如果用if，判断了一次就跳出循环了。