四数之和

四数之和

Zhou Shouyu
#算法笔记 #哈希
Table of Contents

给你一个由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

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

题目链接

文章讲解

思路

相比于三数之和，这道题将三元组升为四元组，target由 0 变为自定义。整体思路不变，不过有些细节需要注意。

可以两层 for 循环k,i，然后找剩余元素中和为target - nums[k] - nums[i]的两个元素。使用双指针。

由于target自定义，因此剪枝k时就不能只写nums[k] > target，因为比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝，逻辑变成nums[k] > target && (nums[k] >=0 || target >= 0)就可以了。

同理 剪枝i时需要变为nums[k] + nums[i] > target && nums[k] + nums[i] >= 0。其余内部不变

代码实现

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size(); k++) {
            if (nums[k] > target && nums[k] > 0)
                break;
            if (k > 0 && nums[k] == nums[k - 1])
                continue;
            for (int i = k + 1; i < nums.size(); i++) {
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0)
                    break;
                if (i > k + 1 && nums[i] == nums[i - 1])
                    continue;
                int left = i + 1;
                int right = nums.size() - 1;
                while (left < right) {
                    long sum =
                        (long)nums[k] + nums[i] + nums[left] + nums[right];
                    if (sum == target) {
                        result.push_back(
                            {nums[k], nums[i], nums[left], nums[right]});
                        // 跳过重复的 left
                        while (left < right && nums[left] == nums[left + 1])
                            left++;
                        // 跳过重复的 right
                        while (left < right && nums[right] == nums[right - 1])
                            right--;
                        left++;
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return result;
    }
};
Avatar