15 - 三数之和

题目描述

审题：这个这个，似曾相识呀，诶不就是第一题两数之和嘛
两数之和-传送门
So，可不可以把“三数之和”问题改成“两数之和+X”捏。。。

方法一：利用“两数之和”

计算将列表中每个数与几（target）相加的和为零；
分别使用这个target作为两数之和问题中的target；

去重之后将符合条件的结果加入返回数组。

class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        l = len(nums)
        ret = []
        for j in range(l):
            target = 0 - nums[j]
            tmp = {}
            for i, a in enumerate(nums):
                if i == j:
                    continue
                if target-a in tmp:
                    re = sorted( [nums[j], nums[tmp[target-a]], nums[i]] ) 
                    if re not in ret:
                        ret.append( re )
                else:
                    tmp[a] = i

        return ret

超时啦啊啊啊啊啊(눈‸눈)

方法二：双指针

将数组排序；
第一层循环遍历元素到倒数第三个；
第二层循环使用双指针向中间靠拢检查；
符合条件且不重复的加入结果数组。

class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        l = len(nums)
        nums.sort()
        ret = []

        for i in range(l - 2):
            # 去重
            if i > 0 and nums[i] == nums[i-1]:
                continue

            # 双指针归位！
            j, k = i + 1, l - 1
            while j < k:
                if nums[i] + nums[j] + nums[k] == 0:
                    ret.append( [nums[i], nums[j], nums[k]] )
                    j += 1
                    k -= 1

                    # 去重
                    while j < k and nums[j] == nums[j-1] :
                        j += 1
                    while j < k and nums[k] == nums[k+1] :
                        k -= 1
                elif nums[i] + nums[j] + nums[k] < 0:
                    j += 1
                else:
                    k -= 1

        return ret