15. 三数之和

https://leetcode-cn.com/problems/3sum/

解法一：

常规思路是用三个游标i，j，k遍历整个数组，找出所有的三三组合，看是否满足。然而这样会有重复。

改进：先排序，对每个找到的组合（i，j，k）各自往后搜寻，跳过相同的元素即可 有点借鉴two sum的做法，反向求之。i遍历整个数组，先设一个target=nums[i]，令设两个游标front = i+1，back = len（nums）-1用这两个数的和与target比较，然后进行调整，直到找到为止。找到后跳过相等的数，防止重复。 此外还需注意，py的for循环与c++的for循环略有不同，主要是i不能在循环体中改变，（见https://blog.csdn.net/u012033124/article/details/80224024，第11条）因此对i的循环改成while语句

为何i的范围是0~n-1？不担心front=i+1越界？

因为有front < back限制。且其实i遍历到n-2就可以停止了。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        i = 0
        while i < len(nums):
            target = -nums[i]
            front, back = i+1, len(nums)-1
            while front < back:
                tmp_sum = nums[front] + nums[back]
                if tmp_sum < target:
                    front += 1
                elif tmp_sum > target:
                    back -= 1
                else:    #找到
                    triple = [nums[i], nums[front], nums[back]]    #创建三元组
                    res.append(triple)
                    while front < back and nums[front] == triple[1]: #跳过与triple[1]重复的
                        front += 1
                    while front < back and nums[back] == triple[2]:   #跳过与triple[2]重复的
                        back -= 1
            while i+1 < len(nums) and nums[i+1] == nums[i]:    #跳过与triplet[0]重复的
                i += 1
            i += 1    #while循环
        return res