最近,hashedin 提出了三元组求和问题,其中三个数字应该相加为目标总和。他们说在 O(n) 内完成。
我已经尝试在 O(n^2) 中做到这一点。首先,我对数组进行了排序,然后为了搜索组合,我必须将滑动窗口技术应用于数组中的所有元素。我无法将其减少到 O(n)。
def threeNumberSum(array, targetSum):
array.sort()
l = len(array)
trip = list()
for i in range(l-2):
left = i+1
right = len(array)-1
while left<right:
currentSum = array[i] + array[left] + array[right]
if currentSum == targetSum:
trip.append([array[i], array[left], array[right]])
left += 1
right -= 1
elif currentSum < targetSum:
left += 1
else:
right -= 1
return trip
此代码实际上返回所有可能的总和组合。但据该公司称,只需要一个三胞胎。不需要所有可能的三元组