I am currently learning dynamic programming and i amlooking for a solution to the 2 sum python problem in O(n) time complexity. Please note that the array include negative integers

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

using the two pointers method

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)

Unfortunately, the solution I have above is in 0(n log(n)) time complexity.

what would be the dynamic programming approach to achieve the above in 0(n) time complexity?

my current dynamic programming approach solution only work when the array is made of only non negative integers.

example

dynamic programming

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 []

CodePudding user response：

Here a solution to get all solutions

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))

the idea is to compute the number that is missing by computing the difference between the current value end the target value. the difference is stack in number_bonds