四数之和.md

18.四数之和

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

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

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

输入：nums = [], target = 0
输出：[]

分析

思路与三数之和一样，比三数之和多了一层循环。时间复杂度O(n^3)

def fourSum(nums, target):
    length = len(nums)
    if length < 4:
        return []
    nums.sort()
    ans = []
    for i in range(length-3):
        if i > 0 and nums[i-1] == nums[i]:
            continue

        # 优化效率，去掉没必要的循环
        if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target:
            # 排序后前四位大于目标值可以直接退出
            break
        if nums[i] + nums[length-3] + nums[length-2] + nums[length-1] < target:
            continue

        for j in range(i+1, length-2):
            if j > i+1 and nums[j-1] == nums[j]:
                continue

            # 优化效率，去掉没必要的循环
            if nums[i] + nums[j] + nums[j+1] + nums[j+2] > target:
                # 排序后前四位大于目标值可以直接退出
                break
            if nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target:
                continue

            L = j + 1
            R = length - 1
            while L < R:
                sum_ = nums[i] + nums[j] + nums[L] + nums[R]
                if sum_ < target:
                    L += 1
                    continue
                elif sum_ > target:
                    R -= 1
                    continue
                else:
                    ans.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 ans