3Sum

3Sum

描述

给定一个数字组成的数组, 找出相加为0的三个数字的所有组合, 不能包含重复的组合

示例:
输入: [-1, 0, 1, 2, -1, -4]
输出: [
  [-1, 0, 1],
  [-1, -1, 2]
]

分析

  1. 直接遍历, n 个数字挑选3个的组合种类有 种, 遍历复杂度为
  2. 寻找3个数字, 他们的和为0, 可以转变为寻找2个数字, 相加之后看另一个符号相反的数字是不是在数组里, 复杂度可以变为, 重复的结果可以用一个哈希表过滤

初次以外, k sum 还有一些别的解法, 这里不介绍了, 能 ac 的解法按照第二个来, 答案在下面

答案

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        m = {}
        n = []
        for i in nums:
            if i not in m:
                m[i] = 1
            else:
                m[i] += 1
            if m[i] > 2:
                continue
            n.append(i)
        nums = n
        res = []

        k = {}

        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                x = nums[i]
                y = nums[j]
                t = -(x + y)
                m[x] -= 1
                m[y] -= 1
                if t in m and m[t] != 0:
                    r = sorted([x, y, t])
                    if str(r) not in k:
                        k[str(r)] = 1
                        res.append(r)
                m[x] += 1
                m[y] += 1
        return res
打赏