LeetCode【0018】四数之和

1 中文题目

给一个由 $n$ 个整数组成的数组 $nums$ ，和一个目标值 $target$ 。请找出并返回满足下述全部条件且不重复的四元组 $[nums[a],nums[b],nums[c],nums[d]]$ （若两个四元组元素一一对应，则认为两个四元组重复）：

• $0\le a,b,c,d<n$
• $a、b、c$ 和 $d$ 互不相同
• $nums[a]+nums[b]+nums[c]+nums[d]==target$
• 可以按 任意顺序 返回答案 。

示例：

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

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

• $1\le nums.length\le 200$
• $-10^9\le nums[i]\le 10^9$
• $-10^9\le target\le 10^9$

2 求解方法：双指针+两层循环

2.1 方法思路

方法核心

将数组排序后，使用两层循环固定前两个数，对剩余区间使用双指针法寻找后两个数，在每一层都采用剪枝和去重优化，避免重复计算。

实现步骤
（1）对数组进行排序
（2）第一层循环固定第一个数：

• 去重跳过重复数字
• 最大最小和剪枝

（3）第二层循环固定第二个数：

• 去重跳过重复数字
• 最大最小和剪枝

（4）使用双指针寻找后两个数：

• 计算四数之和
• 根据和与目标值的比较移动指针
• 找到目标时进行去重

方法示例

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

排序后：[-2,-1,0,0,1,2]

第一轮 i = 0 (nums[i] = -2):
    j = 1 (nums[j] = -1):
        left = 2, right = 5
        sum = -2 + (-1) + 0 + 2 = -1 < 0
        left++
        ...直到找到 [-2,-1,1,2]

第二轮 i = 1 (nums[i] = -1):
    j = 2 (nums[j] = 0):
        找到 [-1,0,0,1]
    ...

最终结果：[[-2,-1,1,2], [-1,0,0,1]]

2.2 Python代码

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        # 排序，为后续双指针和剪枝做准备
        nums.sort()
        n = len(nums)
        result = []
        
        # 第一层循环，固定第一个数
        for i in range(n-3):
            # 去重：跳过相同的第一个数
            if i > 0 and nums[i] == nums[i-1]:
                continue
                
            # 剪枝1：当前最小和超过target，后面的组合更大，直接结束
            if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target:
                break
                
            # 剪枝2：当前最大和小于target，说明需要更大的第一个数
            if nums[i] + nums[n-3] + nums[n-2] + nums[n-1] < target:
                continue
            
            # 第二层循环，固定第二个数
            for j in range(i+1, n-2):
                # 去重：跳过相同的第二个数
                if j > i+1 and nums[j] == nums[j-1]:
                    continue
                    
                # 剪枝3：当前四数最小和超过target，内层循环可以直接break
                if nums[i] + nums[j] + nums[j+1] + nums[j+2] > target:
                    break
                    
                # 剪枝4：当前四数最大和小于target，需要更大的第二个数
                if nums[i] + nums[j] + nums[n-2] + nums[n-1] < target:
                    continue
                
                # 双指针查找剩余两个数
                left, right = j + 1, n - 1
                
                while left < right:
                    # 计算当前四数之和
                    curr_sum = nums[i] + nums[j] + nums[left] + nums[right]
                    
                    if curr_sum == target:
                        # 找到符合条件的组合，加入结果集
                        result.append([nums[i], nums[j], nums[left], nums[right]])
                        
                        # 移动左指针并去重
                        left += 1
                        while left < right and nums[left] == nums[left-1]:
                            left += 1
                            
                        # 移动右指针并去重
                        right -= 1
                        while left < right and nums[right] == nums[right+1]:
                            right -= 1
                            
                    elif curr_sum < target:
                        # 和小于目标值，左指针右移
                        left += 1
                    else:
                        # 和大于目标值，右指针左移
                        right -= 1
        
        return result

2.3 复杂度分析

• 时间复杂度：$O(n^3)$
  • 排序：$O(nlogn)$
  • 第一层循环：$O(n)$
  • 第二层循环：$O(n)$
  • 双指针：$O(n)$
• 空间复杂度：$O(1)$
  • 存储结果的空间：
  • 只使用常数个变量
  • 排序可以原地进行

3 题目总结

题目难度：中等
数据结构：数组
应用算法：双指针