[Leetcode]15. 三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

笨方法：
直觉是问题的关键在于不重复。6个数中任意取3个，总共有20种取法。但如果考虑顺序，则总共有120种取法，计算量会高得多。我记得python中是有排列组合的函数的，应该可以直接拿来用。这里我就不调现成的包了，尝试下手写解决。
我觉得可以先排序，排序之后按前后顺序来取数据，应该可以简化问题。超时了。

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans=[]
        l=len(nums)
        if l<3:
            return []
        nums=sorted(nums) #排序
        for i in range(l-2):
            for j in range(i+1,l-1):
                if 0-nums[i]-nums[j] in nums[j+1:] and [nums[i],nums[j],0-nums[i]-nums[j]] not in ans:
                    ans.append([nums[i],nums[j],0-nums[i]-nums[j]])
        return ans

做了一点改进：将3sum问题分解为2sum问题，总算是没有超时了，但总体的效率还是比较低下。执行用时: 5548 ms, 在3Sum的Python提交中击败了1.35% 的用户。内存消耗: 15.2 MB, 在3Sum的Python提交中击败了3.45% 的用户。

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans=[]
        l=len(nums)
        if l<3:
            return []
        nums=sorted(nums) #排序
        lst=[]
        for i in range(l-2):
            tmp_list=nums[i+1:]
            d={}
            for j,jv in enumerate(tmp_list):
                if -nums[i]-jv in d and [nums[i],-nums[i]-jv,jv] not in ans:
                    ans.append([nums[i],-nums[i]-jv,jv])
                d[jv]=j
        return ans

聪明的方法：
借鉴别人的方法：看来先排序是必备步骤。主要的不同在于：该方法使用了双指针，排序之后双指针往往比较有效。

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort() # 将nums按照从小到大排序
        L = []
        for i in range(len(nums)):
            if nums[i] > 0 : # 最小数不能大于0
                break
            if (i > 0) and (nums[i] == nums[i - 1]): # 不重复
                continue
            j = i + 1
            k = len(nums) - 1
            while(j < k):
                x = nums[i] + nums[j] + nums[k] # 三数之和x
                if x > 0: # x>0,则大数应减小k--
                    k -= 1
                elif x < 0: # x<0,则小数应增加j++
                    j += 1
                else:
                    if (j > i+1) and (nums[j] == nums[j - 1]): # 不重复
                        k -= 1
                        j += 1
                        continue
                    L.append([nums[i], nums[j], nums[k]])
                    k -= 1
                    j += 1

        return L

看来判断重复的方法影响很大，下面这个方法的表现也一般。执行用时: 5256 ms, 在3Sum的Python提交中击败了1.61% 的用户。内存消耗: 15 MB, 在3Sum的Python提交中击败了3.94% 的用户。

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans=[]
        l=len(nums)
        nums=sorted(nums) #排序
        for i in range(l-2):
            if nums[i]>0:#最小数不能为0
                break
            j=i+1
            k=l-1
            while j<k:
                tmp=nums[i]+nums[j]+nums[k]
                if tmp>0:
                    k-=1
                elif tmp<0:
                    j+=1
                else:
                    if [nums[i],nums[j],nums[k]] not in ans:
                        ans.append([nums[i],nums[j],nums[k]])
                    k-=1
                    j+=1
        return ans