我試圖找到一個目標(biāo)總和可以從 Python 中的無限數(shù)字流中找到。數(shù)字是正數(shù)（數(shù)字> 0），唯一且數(shù)字不確定。我相信答案是使用動態(tài)編程或堆，但不能完全弄清楚邏輯。關(guān)于可能的數(shù)據(jù)結(jié)構(gòu)或邏輯流程的任何幫助都可以嘗試。太感謝了。例如 nums = [ 99,85,1,3,6,72,7,9,22,....] targetSum = 27output: TrueExplanation: 1+6+22 = 27(targetSum)
3 回答
米脂
TA貢獻(xiàn)1836條經(jīng)驗 獲得超3個贊
您可以使用一個集合來跟蹤到目前為止在迭代中給出的數(shù)字的所有可能總和。對于每次迭代，將當(dāng)前數(shù)字添加到集合中的每個現(xiàn)有總和以添加到集合中，并將當(dāng)前數(shù)字本身添加到集合中。True當(dāng)目標(biāo)和確實在集合中時返回：
def has_sum(nums, targetSum):
sums = set()
for i in nums:
sums.update([s + i for s in sums if s + i <= targetSum])
if i <= targetSum:
sums.add(i)
if targetSum in sums:
return True
return False
以便：
has_sum([99, 85, 1, 3, 6, 72, 7, 9, 22], 29)
返回True（因為 1 + 6 + 22 = 29），并且：
has_sum([99, 85, 1, 3, 6, 72, 7, 9, 22], 27)
返回False（因為您問題中的預(yù)期輸出不正確）。
守著一只汪
TA貢獻(xiàn)1872條經(jīng)驗 獲得超4個贊
您可以遞歸地嘗試滿足給定序列中有或沒有第一個數(shù)字的目標(biāo)總和，直到給定序列中沒有更多數(shù)字，或者直到給定目標(biāo)總和不再為正（因為您在評論中提到所有給定的數(shù)字是正數(shù)）：
def has_sum(nums, targetSum):
if not nums or targetSum <= 0:
return False
first, *rest = nums
return first == targetSum or has_sum(rest, targetSum - first) or has_sum(rest, targetSum)
以便：
has_sum([99, 85, 1, 3, 6, 72, 7, 9, 22], 29)
返回True（因為 1 + 6 + 22 = 29），并且：
has_sum([99, 85, 1, 3, 6, 72, 7, 9, 22], 27)
返回False（因為您問題中的預(yù)期輸出不正確）。
編輯：為了避免在每次調(diào)用中將輸入序列減去第一項復(fù)制到性能影響rest，可以使用索引改進(jìn)上面的代碼：
def has_sum(nums, targetSum, index=0):
if index == len(nums) or targetSum <= 0:
return False
num = nums[index]
return num == targetSum or has_sum(nums, targetSum - num, index + 1) or has_sum(nums, targetSum, index + 1)
侃侃無極
TA貢獻(xiàn)2051條經(jīng)驗 獲得超10個贊
我能想到的一個想法是使用緊密圖。您可以執(zhí)行以下操作：
將小于總和的每個數(shù)字元素作為節(jié)點添加到圖中
每個新節(jié)點都連接到圖中已經(jīng)存在的每個其他節(jié)點
添加到圖形后，使用廣度優(yōu)先搜索從最低元素計算總和
我認(rèn)為這個過程很慢
添加回答
舉報
0/150
提交
取消