18.md

题目地址

https://leetcode-cn.com/problems/4sum/

解答1

def fourSum(nums, target):
    """ 四数之和 """
    nums.sort()
    res = []
    for i in range(len(nums) - 3):
        if i > 0 and nums[i - 1] == nums[i]:
            continue
        for j in range(i + 1, len(nums) - 2):
            if j > i + 1 and nums[j - 1] == nums[j]:
                continue
            l = j + 1
            r = len(nums) - 1
            while l < r:
                four_sum = nums[i] + nums[j] + nums[l] + nums[r]
                if four_sum == target:
                    res.append([nums[i], nums[j], nums[l], nums[r]])
                    while l < r and nums[l + 1] == nums[l]:
                        l += 1
                    while l < r and nums[r - 1] == nums[r]:
                        r -= 1
                    l += 1
                    r -= 1
                elif four_sum < target:
                    l += 1
                else:
                    r -= 1
    return res

解答2

def getSum(nums, target, n):
    """ n数之和 """
    res = []
    if n < 2:
        return [[target]] if target in nums else []
    if n == 2:
        i = 0
        j = len(nums) - 1
        while i < j:
            tmp = nums[i] + nums[j]
            if tmp > target:
                j -= 1
            elif tmp < target:
                i += 1
            else:
                res.append([nums[i], nums[j]])
                while i < j and nums[i] == res[-1][0]:  # 注意
                    i += 1
    else:
        for i in range(len(nums) - n + 1):
            if (i and nums[i] == nums[i - 1]) or nums[i] + sum(nums[-n + 1:]) < target:
                continue
            if sum(nums[i:i + n]) > target:
                break
            tmp = getSum(nums[i + 1:], target - nums[i], n - 1)
            if tmp:
                for item in tmp:
                    res.append([nums[i]] + item)
    return res


def fourSum(nums, target):
    nums.sort()
    return getSum(nums, target, 4)