如何使用包含负整数的数组以 O(n) 时间复杂度使用 python 解决二和问题

Question

我目前正在学习动态编程，我正在寻找 O(n) 时间复杂度的 2 sum python 问题的解决方案。请注意，该数组包含负整数

arr = [2,-1,4,7,11]

使用两个指针方法

target = 10 # sum of (-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 0(n log(n))
# space complexity 0(log 1)

不幸的是，我上面的解决方案的时间复杂度是

0(n log(n))

。

在0(n)时间复杂度内实现上述目标的

动态规划

方法是什么？

我当前的动态规划方法解决方案仅在数组仅由非负整数组成时才有效。

示例

动态规划

arr = [1,2,4,6] # non negative integers
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 []

Answer 1

这里有一个解决方案来获取所有解决方案

target = 10  # sum of (-1,11)
arr = [-1,3,2,4,7,11]

def twoSum(arr, target):
    number_bonds = {}
    res=[]
    for index, value in enumerate(arr):
        if value in number_bonds:
            res.append([arr[number_bonds[value]], arr[index]])
        number_bonds[target - value] = index
    return res

print(twoSum(arr,target))

这个想法是通过计算当前值与目标值之间的差值来计算丢失的数量。区别在于

number_bonds

中的堆栈

Answer 2

这是一个基于 ymmx 的解决方案但进行了改进的解决方案：

def twoSum(nums: List[int], target: int) -> List[int]:
    rest_dict = {}
    
    for i in range(len(nums)):
        value = nums[i]

        if value in rest_dict:
            return [i, rest_dict[value]]

这里的想法是：让a和b如

a + b = target

。对于nums中的每个数字

a

，通过计算target - a将

b

保存在字典中。重复该过程，但现在检查下一个值 a' 是否在字典中，这意味着如果

a' = b

并返回它们的索引。