首先放上解法參考labuladong的團(tuán)滅nsum
這里為大家講解的是Python版本的代碼溪烤，其實(shí)總體思路是一樣的废膘，只是我在解題的時(shí)候遇到了一些問(wèn)題(放在本文最后)露该，覺(jué)得有必要和大家分享一下。
2 Sum
求list中和等于target的兩個(gè)數(shù)黔漂，且不能重復(fù)。很自然想到對(duì)數(shù)組進(jìn)行排序后采用雙指針的方法求解：
(對(duì)應(yīng)后面的求和題，我們?cè)谶@里求具體的數(shù)晶默，而不是index)
class soltuion:
def twoSum(self, nums, target):
nums.sort()
res = []
low, high = 0, len(nums) - 1
while low < high:
left, right = nums[low], nums[high]
tmp_sum = left + right
if tmp_sum > target:
# 只要nums[low]等于left，就會(huì)一直增加low航攒，跳過(guò)這些重復(fù)的值
while low < high and nums[low] == left:
low += 1
elif tmp_sum < target:
# 只要nums[high]等于right磺陡，就會(huì)一直減少high，跳過(guò)這些重復(fù)的值
while low < high and nums[high] == right:
right -= 1
else:
res.append([left, right])
# 只要nums[low]等于left漠畜，就會(huì)一直增加low币他，跳過(guò)這些重復(fù)的值
while low < high and nums[low] == left:
low += 1
# 只要nums[high]等于right，就會(huì)一直減少high盆驹，跳過(guò)這些重復(fù)的值
while low < high and nums[high] == right:
hi -= 1
return res
有了2 Sum為基礎(chǔ)圆丹，我們可以用它作為base case去求解3 Sum和4 Sum
3 Sum
求list中和等于target的兩個(gè)數(shù)，且不能重復(fù)躯喇。使用2 Sum作為base case辫封。
三數(shù)求和怎么轉(zhuǎn)換成兩數(shù)求和呢硝枉？很簡(jiǎn)單，遍歷nums中的每一個(gè)數(shù)倦微，將target減掉它妻味，得到的值就可以作為2 Sum的target。
class soltuion:
def threeSum(self, nums, target):
nums.sort()
res = []
l = len(nums)
i = 0
# 這里用i<l-1欣福，是因?yàn)榱舫鲆粋€(gè)加1的位置給twoSum
# 反正twoSum里面也要判斷邊界條件责球，所以就不在這里判斷了
while i < l-1:
# 減掉當(dāng)前數(shù)，用2 Sum去尋找剩下的值
base_cases = self.twoSum(nums, i+1, target-nums[i])
for x in base_cases:
res.append([nums[i] + x])
# 道理同上拓劝，跳過(guò)重復(fù)的值雏逾，剩下區(qū)間的重復(fù)值在twoSum里會(huì)檢查
while i < l-1 and nums[i] == nums[i+1]:
i += 1
i += 1
return res
# 代碼基本同上，除了多了一個(gè)start來(lái)指示low
def twoSum(self, nums, start, target):
res = []
low, high = start, len(nums) - 1
while low < high:
left, right = nums[low], nums[high]
tmp_sum = left + right
if tmp_sum < target:
while low < high and nums[low] == left:
low += 1
elif tmp_sum > target:
while low < high and nums[high] == right:
right -= 1
else:
res.append(left, right)
while low < high and nums[low] == left:
low += 1
while low < high and nums[high] == right:
right -= 1
return res
好了郑临，想必你已經(jīng)猜到怎么去求解4 Sum了栖博。沒(méi)錯(cuò)，就是將它轉(zhuǎn)換成3 Sum厢洞，再由3 Sum轉(zhuǎn)換成2 Sum仇让，一級(jí)一級(jí)地調(diào)用。
4 Sum
class soltuion:
def fourSum(self, nums, target):
nums.sort()
res = []
l = len(nums)
i = 0
# 這里用i<l-1躺翻，是因?yàn)榱舫鲆粋€(gè)加1的位置給twoSum
# 反正twoSum里面也要判斷邊界條件丧叽，所以就不在這里判斷了
while i < l-1:
# 減掉當(dāng)前數(shù)，用3 Sum去尋找剩下的值
base_cases = self.threeSum(nums, i+1, target-nums[i])
for x in base_cases:
res.append([nums[i] + x])
# 道理同上公你，跳過(guò)重復(fù)的值踊淳，剩下區(qū)間的重復(fù)值在twoSum里會(huì)檢查
while i < l-1 and nums[i] == nums[i+1]:
i += 1
i += 1
return res
def threeSum(self, nums,start, target):
nums.sort()
res = []
l = len(nums)
# 3 Sum的起始從4 Sum的下一個(gè)數(shù)開(kāi)始
i = start
while i < l-1:
# 減掉當(dāng)前數(shù)，用2 Sum去尋找剩下的值
base_cases = self.twoSum(nums, i+1, target-nums[i])
for x in base_cases:
res.append([nums[i] + x])
# 道理同上陕靠，跳過(guò)重復(fù)的值嚣崭，剩下區(qū)間的重復(fù)值在twoSum里會(huì)檢查
while i < l-1 and nums[i] == nums[i+1]:
i += 1
i += 1
return res
# 代碼基本同上，除了多了一個(gè)start來(lái)指示low
def twoSum(self, nums, start, target):
res = []
low, high = start, len(nums) - 1
while low < high:
left, right = nums[low], nums[high]
tmp_sum = left + right
if tmp_sum < target:
while low < high and nums[low] == left:
low += 1
elif tmp_sum > target:
while low < high and nums[high] == right:
right -= 1
else:
res.append(left, right)
while low < high and nums[low] == left:
low += 1
while low < high and nums[high] == right:
right -= 1
return res
最后懦傍，我來(lái)講講自己解題時(shí)遇到的“麻煩”*雹舀。(提示：如果你知道Python里for i in range(x)的坑，請(qǐng)無(wú)視以下部分)
請(qǐng)先看出現(xiàn)在4 Sum和3 Sum里的一部分代碼：
while i < l-1:
# 減掉當(dāng)前數(shù)粗俱，用3 Sum去尋找剩下的值
base_cases = self.threeSum(nums, i+1, target-nums[i])
for x in base_cases:
res.append([nums[i] + x])
# 道理同上说榆，跳過(guò)重復(fù)的值，剩下區(qū)間的重復(fù)值在twoSum里會(huì)檢查
while i < l-1 and nums[i] == nums[i+1]:
i += 1
i += 1
我在一開(kāi)始的時(shí)候寸认，并不是用的"while i < l-1"签财，而是用的"for i in range(l)"。乍一看偏塞，好像兩者沒(méi)什么區(qū)別唱蒸，用了for循環(huán)就不需要在最后寫(xiě)"i += 1"了【牡穑可是神汹，提交的結(jié)果就是有重復(fù)的庆捺。于是，我自己寫(xiě)了一個(gè)小的測(cè)試代碼：
a = 10
for i in range(a):
print(i)
while i % 2 == 0:
i += 1
print(i)
print(i)
print('####')
結(jié)果如下：
0
1
1
####
1
1
####
2
3
3
####
3
3
####
...
也就是說(shuō)屁魏，不管我在for循環(huán)里面怎么修改i的值滔以，進(jìn)行下一輪循環(huán)的時(shí)候i還是去range這個(gè)可迭代對(duì)象里取下一個(gè)i值。所以我用for循環(huán)+range會(huì)產(chǎn)生重復(fù)的結(jié)果氓拼，找到原因后你画，就改寫(xiě)為了while循環(huán)。
希望這個(gè)解釋能幫助到你：）
