Table of Content
题目如下：
如果你是按题目顺序进行的练习，那么之前已经多次做个类似的题目了。这类型的题目主要需要注意的地方：
- 将给定输入的数据进行排序后可以更方便的寻找答案
- 避免无效计算（输入的数据长度过小，数据最大N个数总和小于目标或者数据最小N个数的总和大于目标）
- 避免生成重复的答案(跳过 'num[i] == num[i - 1]' ），也可以利用Python的特性，将答案转换为 set 再转换为list来消除重复的答案
- 注意索引的范围
我初次编写的时候采用比较容易想到的解法方案，可以打败50.3%的其他代码，如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
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 |
完成了这道题目后，发现网站上 [[zhuyinghua1203]] 利用了递归的思路给出了这类题目通用的解决算法，挺棒，他给出的参考代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
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 |
