我目前正在學習動態編程，并且正在尋找 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 []
uj5u.com熱心網友回復：
這是一個獲得所有解決方案的解決方案
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
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/488639.html
標籤：Python 数组 python-3.x 算法 数据结构
上一篇：C#洗掉兩個特定字符之間
下一篇：第二次被叫后我的間隔沒有繼續