LeetCode#15 3 Sum

Problem Definition:

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:

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.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

Solution：

1）把数组元素按顺序组织起来，可以避免一顿乱搜。排序至少耗时O(nlogn).

2）要求三个数的和，可以先固定其中一个数，再处理另两个数（变成了two sum）. 时间复杂度至少是O(n^2).

3）为了避免重复的三元组。应该跳过可能引发重复的位置。

1._ 从左边起，把数组第一个数固定为三元组的中的一个数。从这个元素的下一个位置，以及数组尾部开始往里扫。

这里，当前三个数的和为1>0，要减小这个和，就要把right向左移。

2._现在仨数之和为-2<0，因此left向右移。这么重复以上过程，如果找到某个状态，仨数之和为0，保存这仨数的元组。

3._这时得到一个符合条件的三元组(-4, 1, 3). 再接下来，应当使left右移，同时right左移。

4._重复以上过程，直到left>=right。这时将fist往后移动到跟前一个元素不一样的元素的位置，重新开始。

（3._和4._避免找到重复的合格元组）

 1     # @param {integer[]} nums
 2     # @return {integer[][]}
 3     def threeSum(nums):
 4         nums.sort()
 5         res=[]
 6         first=0
 7         finalFirst=len(nums)-3
 8         rightBound=len(nums)-1
 9         while first<=finalFirst:
10             lft=first+1
11             rgt=rightBound
12             nf=nums[first]
13             while lft<rgt:
14                 nl=nums[lft]
15                 nr=nums[rgt]
16                 thr=nf+nl+nr
17                 if thr>0:
18                     rgt-=1
19                 elif thr<0:
20                     lft+=1
21                 else:
22                     res+=[nf, nl, nr],
23                     while lft<rgt and nums[lft]==nl:
24                         lft+=1
25                     while lft<rgt and nums[rgt]==nr:
26                         rgt-=1
27             first+=1
28             while first<=finalFirst and nums[first]==nf:
29                 first+=1
30         return res
31