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: 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]]

思路

暴力的话，时间复杂度是O(n^3）,试了下，肯定不行的，我开始想能不能转换2sum，就是先遍历一遍，求出两个数之和，然后再找这两个数之和存不存在就行。提交了一下，时间上还是过不了，想了半天，就只能用排序的方法，这样的话，我只需要从最左和最右开始找，有点二分的味道。这样的话，最坏情况是O(n^2)。

class Solution(object):    def threeSum(self, nums):        """        :type nums: List[int]        :rtype: List[List[int]]        """        length = len(nums)        nums.sort() #排序        last = length        result = []        for i in range(length - 2):            if(i > 0 and nums[i-1] == nums[i]):                continue #如果i和上次重复了，那么就不用找了！            l,r = i+1,length-1            flag = True            while(l < r):                s = nums[i] + nums[l] + nums[r]                if s < 0:                    l += 1                elif s > 0:                    r -= 1                else:                    result.append([nums[i],nums[l],nums[r]])                    while(l < r and nums[l] == nums[l+1]):                        l += 1                    while(l < r and nums[r] == nums[r-1]):                        r -= 1                    l += 1                    r -= 1        return result