18.四数之和

标签: array, two-pointers, sort

难度: Medium

通过率: 37.17%

原题链接: https://leetcode.com/problems/4sum/description/

题目描述

给定一个包含 $n$ 个整数的数组 $nums$ ，返回所有四元组 $[nums[a], nums[b], nums[c], nums[d]]$ ，使得：

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

返回的答案中，四元组应该是唯一的且可以按任何顺序输出。

解题思路

为了找到所有满足条件的四元组，我们可以采用以下方法：

1. 先排序： 先对数组进行排序。这是因为排序后的数组可以帮助我们避免重复计算同一组合，并且利用排序的性质更方便地确定指针移动方向。

2. 四重循环变双指针： 外层使用两个循环来确定前两个元素（即 nums[a] 和 nums[b]）。对于每一对 (a, b)，我们希望找到另外两个索引 (c, d) 使其满足四数之和等于目标值 target。利用双指针技术，可以用两个指针从 b+1 到数组的结尾进行扫描以找出符合条件的 c 和 d。

3. 去重： 在遍历的过程中，尤其是在确定 a, b, c, d 时，我们需要确保排除重复元素，以避免相同的四元组被计算多次。具体来说，在每次更新 a, b, c, d 时，我们需要跳过任何重复的数。

4. 双指针扫描： 对于给定的 a 和 b, 我们可以使用两个指针（c 指向 b+1 开始，d 从数组结尾开始），通过调整两个指针的位置以查找目标和。如果 nums[c] + nums[d] 太小，说明需要增大和，可以将 c 右移一位；如果太大，则将 d 左移一位。否则，如果刚好等于目标值，需要将该四元组加入结果中，并同时移动两个指针以避免重复。

此方法最坏情况下的时间复杂度为 $O(n^3)$，但由于数组排序可以帮助我们有效地避开不必要的计算，实际表现常常更为优越。

代码实现

Python

def fourSum(nums, target):
    nums.sort()  # 对数组进行排序
    results = []
    length = len(nums)
    
    for i in range(length - 3):
        # 去重，如果当前数与前一个数相同，我们就可以跳过
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        for j in range(i + 1, length - 2):
            # 去重，如果当前数与前一个数相同，我们就可以跳过
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue
            
            left, right = j + 1, length - 1
            while left < right:
                total = nums[i] + nums[j] + nums[left] + nums[right]
                if total < target:
                    left += 1
                elif total > target:
                    right -= 1
                else:
                    results.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
    
    return results

C++

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());  // 对数组进行排序
        vector<vector<int>> results;
        int length = nums.size();

        for (int i = 0; i < length - 3; ++i) {
            // 去重，如果当前数与前一个数相同，我们就可以跳过
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            for (int j = i + 1; j < length - 2; ++j) {
                // 去重，如果当前数与前一个数相同，我们就可以跳过
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;

                int left = j + 1, right = length - 1;
                while (left < right) {
                    long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum < target) {
                        ++left;
                    } else if (sum > target) {
                        --right;
                    } else {
                        results.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;
                    }
                }
            }
        }
        return results;
    }
};

JavaScript

function fourSum(nums, target) {
    nums.sort((a, b) => a - b);  // 对数组进行排序
    const results = [];
    const length = nums.length;

    for (let i = 0; i < length - 3; i++) {
        // 去重
        if (i > 0 && nums[i] === nums[i - 1]) continue;

        for (let j = i + 1; j < length - 2; j++) {
            // 去重
            if (j > i + 1 && nums[j] === nums[j - 1]) continue;

            let left = j + 1, right = length - 1;
            while (left < right) {
                const sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum < target) {
                    left++;
                } else if (sum > target) {
                    right--;
                } else {
                    results.push([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--;
                }
            }
        }
    }

    return results;
}

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);  // 对数组进行排序
        List<List<Integer>> results = new ArrayList<>();
        int length = nums.length;

        for (int i = 0; i < length - 3; i++) {
            // 去重
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            for (int j = i + 1; j < length - 2; j++) {
                // 去重
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;

                int left = j + 1, right = length - 1;
                while (left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum < target) {
                        left++;
                    } else if (sum > target) {
                        right--;
                    } else {
                        results.add(Arrays.asList(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--;
                    }
                }
            }
        }
        return results;
    }
}

复杂度分析

• 时间复杂度： $O(n^3)$，其中 $n$ 是数组的长度。排序需要 $O(n \log n)$ 的时间，而随后使用三重循环和两个指针遍历组合则总需 $O(n^3)$ 的时间。
• 空间复杂度： $O(1)$，不计结果集的存储，算法使用的额外空间与输入大小无关。排序操作在某些情况下可能需要 O(log n) 的栈空间。