Nsum问题

题目

题解

暴力法

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        if len(nums) < 4:
            return []
        nums.sort()
        N = len(nums)
        res = []
        for i in range(N-3):
            for j in range(i+1, N-2):
                for k in range(j+1, N-1):
                    for m in range(k+1, N):
                        tmp = [nums[i], nums[j], nums[k], nums[m]]
                        if sum(tmp) == target and tmp not in res:
                            res.append(tmp)
        return res

双指针

class Solution:
    def Nsum(self, nums: List[int], N, start, target):
        """
        Params:
            nums: 输入列表
            n: 求几个数之和，n=2 两数之和， n=3三数之和
            start: 从列表的第几个元素开始搜索
            target: 之和要为多少
        """ 
        nums.sort()
        res = []
        n = len(nums)
        # 至少是 2Sum，且数组大小不应该小于 n
        if n < 2 or n < N:
            return res
        # 2Sum 是 base case
        if N == 2:
            lo, hi = start, n - 1
            while lo < hi:
                left, right = nums[lo], nums[hi]
                if left + right == target:
                    res.append([left, right])
                    # 左边相同的元素移动
                    while lo < hi and nums[lo] == left:
                        lo += 1
                    # 左边相同的元素移动
                    while lo < hi and nums[hi] == right:
                        hi -= 1
                elif left + right > target:
                    while lo < hi and nums[hi] == right:
                        hi -= 1
                elif left + right < target:
                    while lo < hi and nums[lo] == left:
                        lo += 1
        # n > 2 时，递归计算 (n-1)Sum 的结果
        else:
            i = start
            # 遍历整个列表
            while i < n:
                left = nums[i]
                sub = self.Nsum(nums, N-1, i+1, target-nums[i])
                for item in sub:
                    res.append([left] + item)
                while i < n and nums[i] == left:
                    i += 1

        return res

    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        res = self.Nsum(nums, 4, 0, target)
        return res