18. 四数之和（Python）

【题目】

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

【示例】

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

【解答】

这里我们直接引用[zhuyinghua1203]大佬的代码，解决N数之和的问题。笔者认为，这段代码是真正的优秀。


class Solution:

    def twoSum(self, nums, target=0):
        return self.NSum(nums, target, 2)

    def threeSum(self, nums, target=0):
        return self.NSum(nums, target, 3)

    def fourSum(self, nums, target=0):
        return self.NSum(nums, target, 4)

    def NSum(self, nums, target, n):
        nums.sort()
        results = []
        self.findNsum(nums, target, n, [], results)
        return results

    def findNsum(self, nums, target, N, result, results):
        """
        寻找N数之和的所有可能性
        该函数没有返回值，但是会修改输入的results变量，用户使用时直接从该变量中获取结果即可
        :param nums: 输入原始数组
        :param target: 目标值
        :param N: 加数个数
        :param result: 用于递归过程暂存结果，输入[]即可
        :param results: 结果会被添加到该变量中，输入值为“[]”的变量即可
        :return: None
        """

        if len(nums) < N or N < 2:
            return

        # 解决两数之和问题
        if N == 2:
            l, r = 0, len(nums)-1                               # 初始化左指针l和右指针r
            while l < r:
                if nums[l] + nums[r] == target:
                    results.append(result + [nums[l], nums[r]]) # 把当前组合添加到结果列表results

                    # 将左指针向右移动到与当前对应数字不同的位置
                    l += 1
                    while l < r and nums[l] == nums[l - 1]:
                        l += 1

                    # 将右指针向左移动到与当前对应数字不同的位置
                    r -= 1
                    while r > l and nums[r] == nums[r + 1]:
                        r -= 1

                elif nums[l] + nums[r] < target:                # 如果两数之和小于目标值
                    l += 1                                      # 左指针右移

                else:                                           # 如果两数之和大于目标值
                    r -= 1                                      # 右指针左移

        # 将N数之和问题转变为N-1数之和问题
        else:
            # 逐一去掉数组中的最小数，直到只剩N个数，注意范围，i从0开始到len(nums)-N
            for i in range(0, len(nums)-N+1):
                # 利用排序的优势，如果N个最小数之和已经比目标值大，或N个最大值之和也比目标值小，
                # 那么当前数组及之后循环的数组一定无法满足条件，直接跳出所有循环
                if target < nums[i]*N or target > nums[-1]*N:
                    break

                # 为了避免重复，如果当前和上一个数相同，则直接开始下一个循环，
                if i == 0 or i > 0 and nums[i-1] != nums[i]:

                    # 寻找N-1数之和的结果，需要注意这里参数的修改
                    # 在数组nums[i+1:]中寻找目标为target-nums[i]的N-1设数之和的所有可能性
                    self.findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
        return


if __name__ == "__main__":
    s = Solution()
    print(s.threeSum([1,0,-1,0,-2,2]))
    print(s.fourSum([1,0,-1,0,-2,2]))

执行用时 : 128 ms, 在4Sum的Python3提交中击败了91.20% 的用户
内存消耗 : 12.9 MB, 在4Sum的Python3提交中击败了98.48% 的用户

如有疑问或建议，欢迎评论区留言~

最后编辑于：2019.05.08 09:51:56