Python求解含负数数组两数之和O(n)动态规划解法

你目前在学习动态规划（dynamic programming），要找支持负整数输入、时间复杂度O(n)的Python两数和解法，测试用例为arr = [2,-1,4,7,11]。

现有方案的问题 #

双指针法 #

你写的双指针实现如下：

target = 10 # 预期匹配数对 (-1,11)

def two_sum(arr, target):
  arr.sort()
  left = 0
  right = len(arr)-1
  while left < right:
    current_sum = arr[left] + arr[right]
    if current_sum == target:
       return [arr[left], arr[right]]
    elif current_sum < target:
      left += 1
    elif current_sum > target:
      right -= 1
  return []

# time complexity O(n log(n))
# space complexity 原注释写的O(log 1)为笔误

这个解法因为要先对数组排序，时间复杂度是O(n log(n))，达不到O(n)的要求。

你写的“仅支持非负整数”的DP版本 #

这个版本跑不通负数根本不是思路问题，是代码里字典的键值写反了：

arr = [1,2,4,6] # 非负整数测试用例
target = 3

def two_sum(arr, target):
  seen = {}
  for idx, value in enumerate(arr):
    remaining = target - value
    if remaining in seen:
      return [seen[remaining], value]
    seen[idx] = value # 错误点：把索引存成了字典的键，值存成了元素
  return []

你把字典的键设成了数组索引，值存成元素值，判断remaining in seen的时候，实际是在查「需要的差值是不是等于某个数组索引」，只有当元素值刚好和索引值重合的时候才能碰巧跑通，和数组有没有负数完全没关系。

正确实现 #

哈希表存储遍历记录本身就是动态规划的思路——把已经遍历过的子问题结果（见过的数值）存在表中，避免重复计算，全程只需要遍历一次数组，时间复杂度严格O(n)，天然支持负整数、0、正整数的所有场景。

def two_sum(arr, target):
    # dp表：key为已经遍历过的元素值，value标记该值存在
    seen = dict()
    for value in arr:
        # 计算当前值凑出target需要的另一个数
        need = target - value
        if need in seen:
            return [need, value]
        # 没找到匹配就把当前值存入dp表
        seen[value] = True
    # 遍历完无匹配返回空列表
    return []

# 测试带负数的用例
arr = [2,-1,4,7,11]
target = 10
print(two_sum(arr, target)) # 输出 [-1, 11]，符合预期

如果需要返回数对的索引而不是具体值，只需要调整dp表存储的内容即可，逻辑完全不变：

def two_sum_index(arr, target):
    seen = dict()
    for idx, value in enumerate(arr):
        need = target - value
        if need in seen:
            return [seen[need], idx]
        seen[value] = idx
    return []

• 时间复杂度：O(n)，仅做一次数组遍历，字典的插入、查询操作平均时间复杂度均为O(1)
• 空间复杂度：O(n)，最坏情况需要存储全部数组元素

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