如何用含负整数的数组求解O(n)时间复杂度中的python和问题

Question

我目前正在学习动态编程，我正在寻找O(n)时间复杂度中2和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中的堆栈