python 四数之和 多种解法

方法一：暴力枚举

暴力枚举方法比较容易想到，就是将四个数的组合进行遍历，找到符合要求的组合。

代码如下：

def fourSum(nums, target):
    length = len(nums)
    nums.sort()
    result = []
    for i in range(length - 3):
        for j in range(i + 1, length - 2):
            for k in range(j + 1, length - 1):
                for l in range(k + 1, length):
                    if nums[i] + nums[j] + nums[k] + nums[l] == target:
                        if [nums[i], nums[j], nums[k], nums[l]] not in result:
                            result.append([nums[i], nums[j], nums[k], nums[l]])
    return result

时间复杂度为 O(n4)。

方法二：双指针

双指针方法比较高效，可以将时间复杂度降至O(n3)。

首先对数组进行排序，然后固定两个数，再用双指针法找到另外两个数，使其和等于目标值。

代码如下：

def fourSum(nums, target):
    nums.sort()
    n = len(nums)
    res = []
    for i in range(n-3):
        # 跳过重复元素
        if i > 0 and nums[i] == nums[i-1]:
            continue
        # 当前最小值大于目标值或者当前最大值小于目标值，直接退出
        if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target:
            break
        if nums[i] + nums[n-1] + nums[n-2] + nums[n-3] < target:
            continue
        for j in range(i+1, n-2):
            # 跳过重复元素
            if j > i+1 and nums[j] == nums[j-1]:
                continue
            # 当前最小值大于目标值或者当前最大值小于目标值，直接退出
            if nums[i] + nums[j] + nums[j+1] + nums[j+2] > target:
                break
            if nums[i] + nums[j] + nums[n-1] + nums[n-2] < target:
                continue
            # 双指针查找另外两个数
            left, right = j+1, n-1
            while left < right:
                total = nums[i] + nums[j] + nums[left] + nums[right]
                if total == target:
                    res.append([nums[i], nums[j], nums[left], nums[right]])
                    # 跳过重复元素
                    while left < right and nums[left] == nums[left+1]:
                        left += 1
                    while left < right and nums[right] == nums[right-1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif total < target:
                    left += 1
                else:
                    right -= 1
    return res