优选算法：四数目标和（双指针）

Yuzuriha

发布于 2026-01-14 15:50:50

790

文章被收录于专栏：Linux网络Linux网络

题目详情：. - 力扣（LeetCode）

一. 题目解析

题意还是比较好理解的。给一个数组，然后再数组中找到四个重复的数之和刚好等于目标和即可，再其次就是最终返回的结果不能有重复的元组。

二. 算法原理

其实这里的算法原理与我上一篇文章（优选算法：三数目标之和（双指针）-CSDN博客）大致相似，只是这里多了一个大循环而已。大家可以先去看一看这篇文章，以便于更好的理解下面思路。

首先，我们可以先固定一个数，只考虑三个数动态的情况，那其实这里就是求三个数的目标和的问题。而三个数的目标和的方法，其实也就是先固定一个数然后去求动态的两个数。那求两个数就非常好求了。

那么下面讲解具体步骤：

一. 先用sort函数对整个数组进行排序。然后定义出四个指针：fix1 fix2 left right。 fix1作为考虑三个数目标和时所固定的数：fix1=0; fix2作为考虑两个目标和时所固定的数：fix2=fix1+1; left作为考虑动态两个数时的最左边，同理right作为最右边。由于题目要求返回多个数组，所以我们定义一个二维数组ret作为返回结果

二. 首先一个fix1的for循环 fix1<nums.size()-4，在嵌套一个fix2的for循环 fix2<nums.size()-3，然后再嵌套一个 while(left<right)的循环：在这个循环中计算四个数的和，然后与目标值进行比较，如果刚好等于目标值则压入 ret，然后left++ right--。如果大于目标值则 right-- ，然后进入新的循环。如果小于目标值则left++，然后在进循环。当所有循环结束时，代表我们找到了所有的情况

三. 我们找到了所有元素还没有完这道题还没有完。我们还有极为重要的一步：去重。

1.当我们找到符合的四个值时，我们压入元素，然后left 和 right会移动到下一位置，但是如果left和right移动了以后仍是重复的元素的话，我们就需要跳过重复元素才行

跳过重复元素，我们可以借助while循环实现： while(left<right&&nums[left]==nums[left-1]) left++; while(left<right&&nums[right]==nums[right+1]) right--;

2.同理，当left与right相遇时跳出循环，fix2++时。fix2也可能会遇到重复的元素，一旦fix2重复了那么就意味着，这一轮固定的元素与上轮的元素相同，那么就以为着这一轮找到的符合条件的四个元素就一定是重复的。所以fix2也需要跳过循环。

同样的我们也可以借助while循环跳过重复元素：while (fix2 < =nums.zie()-3 && nums[fix2] == nums[fix2-1]) fix2++;

3.同理fix1也会出现重复的情况，也需要跳过重复元素： while (fix1 && fix1 <= size - 3 && nums[fix1] == nums[fix1 - 1]) fix1++;

最后对于这道题，有一个比较坑的点就是使用int类型计算四个元素的和时会溢出

所以我们要用一下 longlong 才不会溢出，这里要注意一下

三. 代码实现

class Solution {
public:
    vector<vector<int>> ret;

    vector<vector<int>> fourSum(vector<int>& nums, int t)
    {
        sort(nums.begin(), nums.end());
        int fix1 = 0;
        int size = nums.size() - 1;
        for (; fix1 <= size - 3;)
        {
            int fix2 = fix1 + 1;
            for (; fix2 <= size - 2;)
            {
                int left = fix2 + 1;
                int right = size;
                while (left < right)
                {
                    long long sum = (long long)nums[left] + nums[right] + nums[fix1] + nums[fix2];
                    if (sum == t)
                    {
                        ret.push_back({ nums[fix1] ,nums[fix2],nums[left],nums[right] });
                        left++;
                        right--;

                        //跳过left right重复元素
                        while (left < right && nums[left] == nums[left - 1])
                            left++;
                        while (left < right && nums[right] == nums[right + 1])
                            right--;
                    }
                    else if (sum > t)
                        right--;
                    else
                        left++;
                }
            //跳过fix2的重复元素
            fix2++;
            while (fix2 > 1 && fix2 <= size - 2 && nums[fix2] == nums[fix2 - 1])
                fix2++;
            }
            //跳过fix1的重复元素
            fix1++;
            while (fix1 && fix1 <= size - 3 && nums[fix1] == nums[fix1 - 1])
                fix1++;
        }
        return ret;
    }
};