时间戳

首页 > 解决方案 > Leetcode 题 '3Sum' 算法超过时限，寻求改进

python - Leetcode 题 '3Sum' 算法超过时限，寻求改进

问题描述

给定一个由 n 个整数组成的数组 nums，在 nums 中是否存在元素 a、b、c 使得 a + b + c = 0？在数组中找到所有唯一的三元组，其总和为零。

class Solution:
    def threeSum(self, nums):

        data = []
        i = j = k =0
        length = len(nums)
        for i in range(length):
            for j in range(length):
                if j == i:
                    continue
                for k in range(length):
                    if k == j or k == i:
                        continue
                    sorted_num = sorted([nums[i],nums[j],nums[k]])
                    if nums[i]+nums[j]+nums[k] == 0 and sorted_num not in data:
                        data.append(sorted_num)

        return data

我的解决方案运行良好，但似乎它可能太慢了。有没有办法在不显着改变代码的情况下改进我的代码？

标签： pythonpython-3.xalgorithm

解决方案

这是一个具有一些优化技巧的 O(n^2) 解决方案：

import itertools

class Solution:
    def findsum(self, lookup: dict, target: int):
        for u in lookup:
            v = target - u
            # reduce duplication, we may enforce v <= u
            try:
                m = lookup[v]
                if u != v or m > 1:
                    yield u, v
            except KeyError:
                pass

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        lookup = {}
        triplets = set()
        for x in nums:
            for y, z in self.findsum(lookup, -x):
                triplets.add(tuple(sorted([x, y, z])))
            lookup[x] = lookup.get(x, 0) + 1
        return [list(triplet) for triplet in triplets]

首先，您需要一个哈希查找来将您的 O(n^3) 算法减少到 O(n^2)。这就是整个想法，其余的都是微优化：

  • 查找表是与对数组的扫描一起构建的，因此它是一次性的
  • 以前见过的唯一项目的查找表索引，因此它可以有效地处理重复项，并且通过使用它，我们将二级循环的迭代次数保持在最低限度

推荐阅读