四数之和-python

四数之和-python

class Solution:
    # 分治法
    def fourSum(self, nums, target):
        # 排序
        nums.sort()
        results = []
        self.findNsum(nums, target, 4, [], results)
        return results

    # tempList 每次固定一个数进行存储
    def findNsum(self, nums, target, N, tempList, results):
        # nums的长度不能少于需要求的长度
        if len(nums) < N or N < 2:
            return
        # 求两数之和
        if N == 2:
            l = 0
            r = len(nums) - 1
            while l < r:
                if nums[l] + nums[r] == target:
                    results.append(tempList + [nums[l], nums[r]])
                    l += 1
                    r -= 1
                    # 去除排序后邻边相同的数
                    while l < r and nums[l] == nums[l - 1]:
                        l += 1
                    while l < r and nums[r] == nums[r + 1]:
                        r -= 1
                elif nums[l] + nums[r] < target:
                    l += 1
                else:
                    r -= 1
        # 固定数 逐层循环 1 1 循环 1 2 循环 1 3 循环 2 1 循环 2 2 循环找合适的值
        else:
            for i in range(0, len(nums)):
                if i == 0 or i > 0 and nums[i - 1] != nums[i]:
                    self.findNsum(nums[i + 1:], target - nums[i], N - 1, tempList + [nums[i]], results)
        return
	
	# 更为直观...
    def fourSum_1(self, nums, target):
        nums.sort()
        res = []
        for i in range(len(nums) - 3):
            # 去除重复项
            if i > 0 and nums[i] == nums[i - 1]:
                # 跳过本次循环，执行下一次
                continue
            for j in range(i + 1, len(nums) - 2):
                # 去除重复项
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                l = j + 1
                r = len(nums) - 1
                while l < r:
                    sum = nums[i] + nums[j] + nums[l] + nums[r]
                    if sum > target:
                        r -= 1
                    elif sum < target:
                        l += 1
                    else:
                        res.append([nums[i], nums[j], nums[l], nums[r]])
                        l += 1
                        r -= 1
                        while l < r and nums[l] == nums[l - 1]:  # 去除重复项
                            l += 1
                        while l < r and nums[r] == nums[r + 1]:  # 去除重复项
                            r -= 1
            return res


result = Solution()
result = result.fourSum([1, 0, -1, 0, -2, 2], 0)
print(result)