3Sum

Given an arraySofnintegers, are there elementsa,b,cinSsuch thata+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.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

这道题让我们求三数之和，比之前那道Two Sum 两数之和要复杂一些，我们还是要首先对原数组进行排序，然后开始遍历排序后的数组，这里注意不是遍历到最后一个停止，而是到倒数第三个就可以了，对于遍历到的数，我们用0减去这个数得到一个sum，我们只需要再之后找到两个数之和等于sum即可，这样一来问题又转化为了求two sum，这时候我们一次扫描，找到了等于sum的两数后，加上当前遍历到的数字，按顺序存入结果中即可.

但是有可能出现重复，那么我们就要分别考虑最外层循环重复的问题，还有里面two sum 循环的重复问题。

最外层循环，如果出现重复那么我们可以直接把这个 loop 给 continue 掉，因为 这个元素作为 target 的 two sum 之前第一次出现时跑的那次循环肯定已经包括了的

two sum 里面循环，假如说有重复这样1,1,2,2。为什么不能直接去重直接把他们给删了呢？ 因为11或者22也有可能是需要的答案

那我们就可以用这个九章老师说的选代表的方法，什么意思呢，我们就规定要优先选择这个数字第一次出现的那次，那么我们左指针和右指针发现重复了以后怎么办呢，我们就继续++ 或者 – 直到不是重复为止.

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums = sorted(nums)
        result = []
        for i in xrange(len(nums)):
            # 去重，别忘了写i>0，也就是i=0的时候不用判断.不能用nums[i]==nums[i+1],会index out of range
            if i>0 and nums[i] == nums[i-1]:
                continue
            target = 0 - nums[i]
            left, right = i+1, len(nums)-1
            while left < right:
                if nums[left] + nums[right] == target:
                    result.append([nums[i], nums[left], nums[right]])
                    # 处理内部去重
                    while left < right and nums[left]==nums[left+1]:
                        left+=1
                    while left < right and nums[right]==nums[right-1]:
                        right-=1
                    left+=1
                    right-=1
                elif nums[left]+nums[right] > target:
                    right-=1
                else:
                    left+=1
        return result

时间 O(n^2)

外面的 sort 是 O(nlogn) 最外层循环 O(n) 里面 two sum 的循环也是 O(n) total = O(nlogn) + O(n^2) 所以我们取最大值 O(n^2)

空间 O(1)

并没有用到额外的空间