时间戳

首页 > 解决方案 > 为什么我的蛮力解决方案比优化的哈希表解决方案更快？

arrays - 为什么我的蛮力解决方案比优化的哈希表解决方案更快？

问题描述

这是我为Python3 中 leetcode 上的二和问题提交的两个解决方案：

蛮力：O(n^2)

运行时间：44 毫秒

内存使用：14.4 MB

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for indx1, val1 in enumerate(nums):
            for indx2, val2 in enumerate(nums[indx1+1:]):
                if val1 + val2 == target:
                    return [indx1, indx2+indx1+1]
        return []

哈希表（dict）解决方案：O（n）

运行时间：52 毫秒

内存使用：14.3 MB

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        h = {}
        for i, num in enumerate(nums):
            n = target - num
            if n not in h:
                h[num] = i
            else:
                return [h[n], i]

我真的不明白为什么蛮力 O(n^2) 比优化的 O(n) 解决方案更快？？！

非常感谢你。

标签： arrayspython-3.xdictionaryhashtable

解决方案

推荐阅读