为何HashMap查找+遍历的两数之和解法时间复杂度为O(N)而非O(N²)？

你实现的两数之和HashMap解法代码如下：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        #nums=[i for i in nums if i<target]
        hashm={}
        hashm[nums[0]]=0
        for i in range(1,len(nums)):
            if (target-nums[i]) in hashm.keys():
                return [hashm[target-nums[i]],i]
            hashm[nums[i]]=i

你疑惑的核心点在于对哈希表查找复杂度的误解：

• Python中的dict（你代码里的hashm）是基于哈希表实现的，平均情况下，键的查找、插入操作时间复杂度都是O(1)，而非O(N)
• 只有在极端哈希冲突场景下（比如所有元素的哈希值完全相同，哈希表退化为链表结构），查找操作才会退化为O(N)的最坏时间复杂度，但这种情况在LeetCode测试用例和实际开发中几乎不会出现，算法复杂度分析通常以平均时间复杂度作为参考标准
• 你的算法只遍历数组一次（时间复杂度O(N)），每次循环内的哈希表操作都是O(1)平均时间，因此整体平均时间复杂度为O(N)，这也是LeetCode和复杂度检测工具给出结果的原因

内容的提问来源于stack exchange，提问作者jai