樣本輸入陣列 = [12, 3, 1, 2, -6, 5, -8, 6] targetSum = 0
樣本輸出 [[-8, 2, 6], [-8, 3, 5], [-6, 1, 5]]
我的代碼如下：
def threeNumberSum(array, targetSum):
array.sort()
for i in range(len(array) - 2):
nums = []
firstNum = array[i]
for j in range(i 1, len(array) - 1):
secondNum = array[j]
for k in range(j 1, len(array)):
thirdNum = array[k]
potentialTarget = firstNum secondNum thirdNum
if potentialTarget == targetSum:
nums.append(firstNum)
nums.append(secondNum)
nums.append(thirdNum)
return [[firstNum, secondNum, thirdNum]]
return []
請建議我應該怎么想。謝謝
uj5u.com熱心網友回復：
您當前的演算法是 O(n^3)。您可以通過迭代所有 2 組合并將其降低到 O(n^2)，并使用 O(1) 哈希查找來查找第三個而不是進行另一個 O(n) 迭代：
def three_num_sum(nums, target):
d = {n: i for i, n in enumerate(nums)}
res = []
for i, x in enumerate(nums[:-2]):
for j, y in enumerate(nums[i 1:-1], i 1):
z = target - x - y
if d.get(z, 0) > j:
res.append([x, y, z])
return res
print(three_num_sum([12, 3, 1, 2, -6, 5, -8, 6], 0))
# [[-8, 2, 6], [-8, 3, 5], [1, -6, 5]]
uj5u.com熱心網友回復：
我認為您應該將結果放在一個串列中，否則您將在找到所有可能性之前結束該功能
def threeNumberSum(array, targetSum):
array.sort()
possibilities = []
for i in range(len(array) - 2):
firstNum = array[i]
for j in range(i 1, len(array) - 1):
secondNum = array[j]
for k in range(j 1, len(array)):
thirdNum = array[k]
potentialTarget = firstNum secondNum thirdNum
if potentialTarget == targetSum:
possibilities.append([firstNum, secondNum, thirdNum])
return possibilities
array = [12, 3, 1, 2, -6, 5, -8, 6]
targetSum = 0
print(threeNumberSum(array,targetSum))
回答
[[-8, 2, 6], [-8, 3, 5], [-6, 1, 5]]
uj5u.com熱心網友回復：
你可以使用itertools：
import itertools
arr = [12, 3, 1, 2, -6, 5, -8, 6]
def threeNumberSum(array, target_sum):
return [perm for perm in itertools.combinations(arr, 3) # you can change the perm number if you want another number combination length.
if sum(perm) == target_sum]
# test
arr = [12, 3, 1, 2, -6, 5, -8, 6]
print(threeNumberSum(arr, target_sum=0))
輸出：
[(3, 5, -8), (1, -6, 5), (2, -8, 6)]
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/485814.html
下一篇：在修改它時使用結構陣列遞回