3Sum

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

前两个解法，思路上大同小异，都是很直接的方法，但并不是最优解：

class Solution:
    # @return a list of lists of length 3, [[val1,val2,val3]]
    def threeSum(self, num):
        if len(num) <= 2:
            return []

        ret = []
        tar = 0
        num.sort()
        i = 0
        while i < len(num) - 2:
            j = i + 1
            k = len(num) - 1
            while j < k:
                if num[i] + num[j] + num[k] < tar:
                    j += 1
                elif num[i] + num[j] + num[k] > tar:
                    k -= 1
                else:
                    ret.append([num[i], num[j], num[k]])
                    j += 1
                    k -= 1
                    # folowing 3 while can avoid the duplications
                    while j < k and num[j] == num[j - 1]:
                        j += 1
                    while j < k and num[k] == num[k + 1]:
                        k -= 1
            while i < len(num) - 2 and num[i] == num[i + 1]:
                i += 1
            i += 1
        return ret

上面的方法，略麻烦，还是看下caikehe的简化写法：

class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        nums.sort()
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l, r = i+1, len(nums)-1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s < 0:
                    l +=1
                elif s > 0:
                    r -= 1
                else:
                    res.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 res

再来一个排序然后二分法的：

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if not nums: return []

        count = {}
        for n in nums: count[n] = count.get(n, 0) + 1

        ans = []
        if 0 in count and count[0] >= 3:
            ans.append([0,0,0])

        nums = sorted(count)
        for i,n in enumerate(nums):
            if not n: continue
            if count[n] >= 2:
                comp = -2*n
                if comp in count and comp != n:
                    ans.append([n]*2 + [comp])
            if n < 0:
                left = bisect.bisect_left(nums, -n - nums[-1], i+1)
                right = bisect.bisect_right(nums, -n // 2, left)
                for j in nums[left:right]:
                    comp = -n - j
                    if comp in count and comp != j:
                        ans.append([n,j,comp])
        return ans

如果是这类问题，还是推荐这里的最优解，是将3sum的问题转化为2sum的问题：

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 创建一个存储结果的列表
        res = []
        # 创建一个字典用于存储nums中的元素及其出现的次数
        d = dict()
        for i in nums:
            d[i] = d.get(i, 0) + 1
        # 创建两个列表分别用于存储正数和负数
        posnum = [i for i in d if i > 0]
        negnum = [i for i in d if i < 0]
        # 如果nums中全为0，则返回0；
        if d.get(0, 0) > 2:
            res.append([0, 0, 0])
        if negnum == [] or posnum == []:
            return res
        # 分别对正数和负数两个列表中的值进行判断

        for i, x in enumerate(posnum):
            if d[x] >= 2 and -2 * x in d:
                res.append([x, x, -2 * x])
            for y in posnum[i + 1:]:
                if -(x + y) in d:
                    res.append([x, y, -x - y])
        for i, x in enumerate(negnum):
            if d[x] >= 2 and -2 * x in d:
                res.append([x, x, -2 * x])
            for y in negnum[i + 1:]:
                if -(x + y) in d:
                    res.append([x, y, -x - y])
        # 三个数之中有一个数为0 的情况
        if 0 in d:
            for x in posnum:
                if -x in d:
                    res.append([x, 0, -x])
        return res