文章目錄
- 2sum問題
- 3sum問題
- Nsum問題
2sum問題
給定一個陣列，以及一個數，從陣列里隨即找兩個數加起來等于給定的那個數，
找出每組符合條件的數（不可重復），
這表述沒有問題吧，
那，這樣的題目該怎么實作呢？
如果看過上一篇，的上一篇的小伙伴應該很快就能想到用雙指標吧（其實那篇我就想寫這個了，但是想了想，還是憋住了）
這里有兩個地方要注意：
1、陣列要有序
2、跳過同類項
然后，就沒什么難度了吧，我把偽代碼寫一下：
def two_sum(sum,nums):
ret = []
sz = len(nums)
i = 0
j = sz-1
while i<j:
if nums[i]+nums[j] == sum:
ret.append([nums[1],nums[j]])
elif nums[i]+nums[j] > sum:
while nums[j-1] == nums[j]:
j-=1
j-=1
else:
while nums[i+1] == nums[i]:
i+=1
i+=1
return ret
3sum問題
兩數和解決了，接下來就該輪到三數和問題了，三數和，其實就是兩數和的一個增強版本，那么，我們需要做的就是：將三數和降維到兩數和，
如何降維呢？其實也不難，就是拿一個數釘在陣列（標兵）中，剩下兩個數和最終目標減去標兵值，就是兩數和嘛，
這里需要注意：
1、target = target - nums[flag]
2、如果target<0，立即停止
3、新陣列區間：nums[flag+1:]
捋一下，然后我們來實作：
def three_sum(sum,nums):
sz = len(nums)
ret = []
for flag in nums:
if sum<=flag:
return ret
ret.append(flag,two_sum(sum-flag,nums[flag+1:]))
return ret
Nsum問題
三數和解決了，四數和呢？
那不是和三數和一個道理嘛，釘住一個，就變成三數和了，
那五數和呢？釘住一個，變四數和，
六數呢？七數呢？···· N數呢？
不就這樣一路向下遞回了嘛，
這里啊，有個小變通，
如果陣列長度不夠（這個上面倒是忘了，這里說一下）
如果N比陣列長度的一半要長，那不妨反過來，先對陣列求和，接下來你懂得，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/262933.html
標籤：python