一个方法解决nSum 问题

相关题目：
1. 两数之和
15. 三数之和
18. 四数之和

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        # 一定要先排序
        nums.sort()
        return self.nSumTarget(nums, target, 4, 0)

    #注意：调用这个函数之前一定要先给 nums 排序。n 填写想求的是几数之和，
    # start 从哪个索引开始计算（一般填 0），target 填想凑出的目标和。
    def nSumTarget(self, nums, target, n, start) -> List[List[int]]:
        sz = len(nums)
        res = []
        if n<2 or len(nums)<2:
            return res

        # base case  2Sum
        if n == 2:
            lo, hi = start, sz-1
            while lo < hi:
                left, right = nums[lo], nums[hi]
                sum_2 = left + right
                if sum_2 > target:
                    while lo < hi and nums[hi] == right:
                        hi -= 1
                elif sum_2 < target:
                    while lo < hi and nums[lo] == left:
                        lo += 1
                else:
                    res.append([left, right])
                    while lo < hi and nums[lo] == left:
                        lo += 1
                    
                    while lo < hi and nums[hi] == right:
                        hi -= 1
                
        else:
            # n > 2 时，递归计算 (n-1)Sum 的结果
            i = start
            while i < sz:
                sub = self.nSumTarget(nums, target-nums[i], n-1, i+1)
                for arr in sub:
                    arr.append(nums[i])
                    res.append(arr)
           
				# 第一个数不能重复
                while i < sz - 1 and nums[i] == nums[i+1]:
                    i += 1
                i += 1

        return res


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
46
47
48
49
50
51
52