leetcode18题解

2025-10-20

leetcode18题解

题目描述

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n a, b, c, and d are distinct. nums[a] + nums[b] + nums[c] + nums[d] == target You may return the answer in any order.

解题思路

关于采用双指针进行双端遍历的思路，请参考leetcode15 这里将原来位于中间的单个指针i替换为i和j两个指针。一样可以使用，这个部分请读者自行思考。

这里的难点在于如何处理重复值的一个一个簇。

  • 对于有两个相同值的簇 x x x x a a x x x x 由于i在到达这个簇之前已经进行过i在前面的x上的过程。因此当i到达这个簇之后，需要考虑的是i和j同时在这个簇上，和i在这个簇，j在后面的x的情况。
  • 对于有三个以上相同值的簇 x x x x a a a a a a x x x x 由于允许四个值在相同的簇上，因此可以先找三个值都在这个簇上的情况，用循环遍历一遍即可。然后把i和j放在这个簇的两端，进行一次双指针遍历。最后把i放到最右边的位置，j在后面的x上。

    代码实现

class Solution {
    typedef long long ll;
private:
    // 提取重复的四数查找逻辑为函数
    inline void findQuadruples(const vector<int>& nums, int& lp, int& rp, int i, int j, ll target, vector<vector<int>>& res) {
        int lastlp = INT_MIN;
        int lastrp = INT_MAX;
        while (lp < i && j < rp) {
            ll sum = ll(nums[lp]) + nums[i] + nums[j] + nums[rp];
            if (sum > target) {
                lastrp = nums[rp];
                while (lastrp == nums[--rp] && lp < i && j < rp);
            } else if (sum < target) {
                lastlp = nums[lp];
                while (lastlp == nums[++lp] && lp < i && j < rp);
            } else {
                res.push_back({nums[lp], nums[i], nums[j], nums[rp]});
                lastlp = nums[lp];
                while (lastlp == nums[++lp] && lp < i && j < rp);
            }
        }
    }

public:
    vector<vector<int>> fourSum(vector<int>& nums, ll target) {
        int size = nums.size();
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());

        int i = 0;
        int j = i + 1;
        int lp = 0;
        int rp = size - 1;
        int lasti = INT_MIN;
        int lastj = INT_MIN;

        while (i < (size - 2)) {
            lastj = INT_MIN;
            j = i + 1;

            if (i < (size - 2)) {
                int count = 0;
                lasti = nums[i];
                for (int k = i; k < size && nums[k] == lasti; k++, count++);

                if (count == 1) {

                } 
                else if (count == 2) {
                    lp = 0;
                    rp = size - 1;
                    findQuadruples(nums, lp, rp, i, j, target, res);
                    i++;
                    j = i + 1;
                } 
                else {
                    for (int k = 0; k < size; k++) {
                        if (k >= i && k < i + 3) continue;
                        if (ll(nums[k]) + ll(nums[i]) * 3 == target) {
                            res.push_back({nums[i], nums[i], nums[i], nums[k]});
                            break;
                        }
                    }
                    j = i + count - 1;

                    lp = 0;
                    rp = size - 1;
                    findQuadruples(nums, lp, rp, i, j, target, res);
                    i = j;
                    j = i + 1;
                }
            }

            if (i >= size - 2) break;

            lastj = INT_MIN;
            while (j < (size - 1)) {
                lp = 0;
                rp = size - 1;
                findQuadruples(nums, lp, rp, i, j, target, res);
                lastj = nums[j];
                while (lastj == nums[++j] && j < (size - 1));
            }

            lasti = nums[i];
            while (lasti == nums[++i] && i < size - 1);
        }

        return res;
    }
};