Medium

题目描述

给你一个由 n 个整数组成的数组 nums，和一个目标值 target。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]：

  • 0 <= a, b, c, d < n
  • a、b、c 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按任意顺序返回答案。

示例 1：

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

示例 2：

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

提示：

  • 1 <= nums.length <= 200
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9

解题思路

解题思路

四数之和是三数之和的扩展，我们可以通过类似的方法来解决。主要思路是将四数之和转化为三数之和，再转化为两数之和问题。

基本思路：

  1. 排序：首先对数组进行排序，这样便于去重和使用双指针法。

  2. 固定两个数：外层使用两重循环固定前两个数 nums[i] 和 nums[j]，其中 i < j。

  3. 双指针查找：对于剩下的部分，使用双指针法在 [j+1, n-1] 区间内寻找两个数，使得四个数的和等于目标值。

  4. 去重处理：

    • 对于第一个数，如果 nums[i] == nums[i-1] 则跳过
    • 对于第二个数，如果 nums[j] == nums[j-1] 则跳过
    • 找到答案后，移动双指针时也要跳过重复元素

  5. 剪枝优化：

    • 如果当前最小的四个数之和大于 target，直接 break
    • 如果当前数与最大的三个数之和小于 target，continue

这种方法的时间复杂度为 O(n³)，空间复杂度为 O(1)（不考虑结果数组）。

代码实现

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        int n = nums.size();
        if (n < 4) return result;
        
        sort(nums.begin(), nums.end());
        
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            
            // 剪枝：最小四数之和大于target
            if ((long long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
            // 剪枝：最大四数之和小于target
            if ((long long)nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue;
            
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                
                // 剪枝：最小四数之和大于target
                if ((long long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
                // 剪枝：最大四数之和小于target
                if ((long long)nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) continue;
                
                int left = j + 1, right = n - 1;
                while (left < right) {
                    long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        result.push_back({nums[i], nums[j], nums[left], nums[right]});
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        result = []
        n = len(nums)
        if n < 4:
            return result
        
        nums.sort()
        
        for i in range(n - 3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            
            # 剪枝：最小四数之和大于target
            if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:
                break
            # 剪枝：最大四数之和小于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
                
                # 剪枝：最小四数之和大于target
                if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target:
                    break
                # 剪枝：最大四数之和小于target
                if nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target:
                    continue
                
                left, right = j + 1, n - 1
                while left < right:
                    current_sum = nums[i] + nums[j] + nums[left] + nums[right]
                    if current_sum == target:
                        result.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 current_sum < target:
                        left += 1
                    else:
                        right -= 1
        
        return result

public class Solution {
    public IList<IList<int>> FourSum(int[] nums, int target) {
        IList<IList<int>> result = new List<IList<int>>();
        int n = nums.Length;
        if (n < 4) return result;
        
        Array.Sort(nums);
        
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            
            // 剪枝：最小四数之和大于target
            if ((long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
            // 剪枝：最大四数之和小于target
            if ((long)nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue;
            
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                
                // 剪枝：最小四数之和大于target
                if ((long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
                // 剪枝：最大四数之和小于target
                if ((long)nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) continue;
                
                int left = j + 1, right = n - 1;
                while (left < right) {
                    long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        result.Add(new List<int> { nums[i], nums[j], nums[left], nums[right] });
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        
        return result;
    }
}

var fourSum = function(nums, target) {
    const result = [];
    const n = nums.length;
    if (n < 4) return result;
    
    nums.sort((a, b) => a - b);
    
    for (let i = 0; i < n - 3; i++) {
        if (i > 0 && nums[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n³)两层循环固定前两个数，双指针遍历剩余数组
空间复杂度O(1)只使用常数额外空间（不计算结果数组）

相关题目