Given an array nums of n integers, are there elements a, b, c in nums 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. 

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

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

越来越辣鸡……

想了半天才想明白和2-sum是一样用双指针的

纠结半天不知道怎样去重

if(q not in ans)超时 想起对象说过这句话的内部实现肯定是o(n)的

然后知道最外层的要遍历 遍历的时候遇到和之前一样的就continue怎么就不知道了

外层遇到相同的continue里层也是一样的啊！！

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans=[]
        nums.sort()
        for i in range(len(nums)):
            if(i!=0 and nums[i]==nums[i-1]):
                continue
            j=i+1
            k=len(nums)-1
            q=[]
            while(j<k):
                if(nums[j]+nums[k]+nums[i]>0):
                    k=k-1
                elif(nums[j]+nums[k]+nums[i]<0):
                    j=j+1
                else:
                    q=[nums[i],nums[j],nums[k]]
                    ans.append(q)
                    while(j<k and nums[j]==nums[j+1]):
                        j=j+1
                    while(j<k and nums[k]==nums[k-1]):
                        k=k-1
                    k=k-1
                    j=j+1
        return ans