15. 三数之和

15. 三数之和

题目

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]

提示：

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 10^5

题解

很直观的想法，先二重循环取两个数 i,j，然后看剩下的数 k=-i-j 有没有在数组中。

优化1

• 判断数字是否在数组中可以通过hash来加速
• 把同一数字出现3次以上的部分删除掉

这两点可以通过一个字典来实现，字典中储存着该数字出现的次数。
然后根据字典序生成简化后的数组。

优化2

为了删除重复方案，我们得到的三元组顺序要按从小到大来排，所以如果剩下的数 k 小于第二个数 j，那么就舍弃这种方案。
另外，我们要判断第三个数 k 是否已经被前面两个占用，通过 D[k] >= (i == k)+(j == k)+1 来判断。

优化3

构建hash映射，判断得到的新方案是否已在原列表中，事实证明，这个对用时影响很大，优化后差不多快了10倍。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        D = {}
        List_table = {}
        nums.sort()
        Nums = []
        ans = []

        def hash_map(L):
            return L[0]+L[1]*907+L[2]*10007

        for i in nums:
            D[i] = min(D.get(i, 0)+1, 3)

        for i in sorted(D):
            for _ in range(D[i]):
                Nums.append(i)

        for idx, i in enumerate(Nums):
            for j in Nums[idx+1:]:
                k = -i-j
                if k >= j and k in D and D[k] >= ((i == k)+(j == k)+1):
                    if hash_map([i, j, k]) not in List_table:
                        ans.append([i, j, k])
                        List_table[hash_map([i, j, k])] = 1
        return ans

另一种方案

这个差不多是按官方标准答案的思路来的

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res = []
        if n < 3:
            return []
        nums.sort()
        for i in range(n):
            if nums[i] > 0 :
                return res
            if i > 0 and nums[i] == nums[i-1]:
                continue  # continue让程序跳出本次循环，进行下一轮循环
            L = i+1
            R = n-1
            while L < R:
                s = nums[i] + nums[L] + nums[R] 
                if s == 0:
                    res.append([nums[i], nums[L], nums[R]])
                    L += 1
                    R -= 1
                    while L<R and nums[L] == nums[L-1]:
                        L += 1
                    while L<R and nums[R] == nums[R+1]:
                        R -= 1
                elif  s < 0:
                    L += 1
                else:
                    R -= 1
        return res