題目如下：
題目
如果你是按題目順序進(jìn)行的練習(xí)腌零，那么之前已經(jīng)多次做個(gè)類(lèi)似的題目了。這類(lèi)型的題目主要需要注意的地方：
- 將給定輸入的數(shù)據(jù)進(jìn)行排序后可以更方便的尋找答案
- 避免無(wú)效計(jì)算（輸入的數(shù)據(jù)長(zhǎng)度過(guò)小唆阿，數(shù)據(jù)最大N個(gè)數(shù)總和小于目標(biāo)或者數(shù)據(jù)最小N個(gè)數(shù)的總和大于目標(biāo)）
- 避免生成重復(fù)的答案(跳過(guò) 'num[i] == num[i - 1]' ）益涧，也可以利用Python的特性，將答案轉(zhuǎn)換為 set 再轉(zhuǎn)換為list來(lái)消除重復(fù)的答案
- 注意索引的范圍
我初次編寫(xiě)的時(shí)候采用比較容易想到的解法方案驯鳖，可以打敗50.3%的其他代碼闲询，如下：
class Solution:
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
nums = sorted(nums)
res = []
if not nums or len(nums) < 4:
return res
if nums[0] + nums[1] + nums[2] + nums[3] > target:
return res
if nums[-1] + nums[-2] + nums[-3] + nums[-4] < target:
return res
for i in range(0, len(nums)):
if nums[i] + nums[-1] + nums[-2] + nums[-3] < target:
continue
for j in range(i + 1, len(nums) - 2):
if nums[i] + nums[j] + nums[-2] + nums[-1] < target:
continue
x = j + 1
y = len(nums) - 1
while x < y:
if nums[i] + nums[j] + nums[x] + nums[y] == target:
res.append([nums[i], nums[j], nums[x], nums[y]])
x = x + 1
while x < y and nums[x] == nums[x - 1]:
x = x + 1
elif nums[i] + nums[j] + nums[x] + nums[y] < target:
x = x + 1
else:
y = y - 1
rr = []
for r in res:
if r not in rr:
rr.append(r)
return rr
完成了這道題目后，發(fā)現(xiàn)網(wǎng)站上 [[zhuyinghua1203]] 利用了遞歸的思路給出了這類(lèi)題目通用的解決算法浅辙，挺棒扭弧，他給出的參考代碼如下：
def fourSum(self, nums, target):
nums.sort()
results = []
self.findNsum(nums, target, 4, [], results)
return results
def findNsum(self, nums, target, N, result, results):
if len(nums) < N or N < 2: return
# solve 2-sum
if N == 2:
l,r = 0,len(nums)-1
while l < r:
if nums[l] + nums[r] == target:
results.append(result + [nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]:
l += 1
while r > l and nums[r] == nums[r + 1]:
r -= 1
elif nums[l] + nums[r] < target:
l += 1
else:
r -= 1
else:
for i in range(0, len(nums)-N+1): # careful about range
if target < nums[i]*N or target > nums[-1]*N: # take advantages of sorted list
break
if i == 0 or i > 0 and nums[i-1] != nums[i]: # recursively reduce N
self.findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
return
ps：如果您有好的建議，歡迎交流 :-D记舆，也歡迎訪問(wèn)我的個(gè)人博客：tundrazone.com
