【优选算法必刷100题】第007~008题（双指针算法）：三数之和、四数之和问题求解

艾莉丝努力练剑

发布于 2025-11-16 20:50:05

120

文章被收录于专栏：C / C++C / C++

007 三数之和

力扣链接：15. 三数之和

力扣题解链接：排序+双指针解决【三数之和】

题目描述：

1.1 题目解析

1.2 思路1：暴力

解法一：暴力求解（会超时）——

时间复杂度：O(n^3)，空间复杂度：O(logn)。

1.3 思路2：排序 + 双指针

1.3.1 算法思路

本题与两数之和类似，是非常经典的面试题。与两数之和稍微不同的是，题目中要求找到所有【不重复】的三元组。那我们可以利用在两数之和那里用的双指针思想，来对我们的暴力枚举做优化：

1、先排序； 2、然后固定一个数a： 3、在这个数后面的区间内，使用「双指针算法」快速找到两个数之和等于a即可。

但是要注意的是，这道题里面需要有【去重】操作——

1、找到一个结果之后，left和[right指针要【跳过重复】的元素； 2、当使用完一次双指针算法之后，固定的a也要【跳过重复】的元素。

1.3.2 代码实现

代码演示：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        //1、排序
        sort(nums.begin(),nums.end());
        //2、固定
        int n = nums.size();
        for(int i = 0;i < n;)
        {
            int left = i + 1,right = n - 1,target = -(nums[i]);
            while(left < right)
            {
                //a <= 0
                if(nums[i] > 0)break;
                int sum = nums[left] + nums[right];
                if(sum > target)right--;
                else if(sum < target)left++;
                else{
                        ret.push_back({nums[i],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--;
                }
            }
            //i查重
            //i在这里移动，不在for循环
            i++;
            while(i < n && nums[i] == nums[i - 1])i++;
        }
        return ret;
    }
};

时间复杂度：O(n^3)，空间复杂度：O(logn)。

1.4 过程推算

本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下！

1.5 反思

总结： 1、没学到STL，vector<vector<int>> ret;和ret.push_back({nums[i],nums[left],nums[right]});这步根本想不到，直接来刷题了，对自己的实力没有清晰的认知（QAQ）； 2、没想到固定的值a <= 0，这个常数级别的小优化想不到； 3、还是去重操作，都在一个条件判断下去重了，left和right在while(left < right)里面去重，i应该在它外面去重，因为刚才我已经让for循环的i++（i移动）这个操作搬到for里面来进行了，这样去重了，这样移动完之后，得到的i就是下一步我要固定的那个数了； 4、i移动的操作在while循环里面搞定，for循环for(int i = 0;i < n;)这个可以空着不写没有想到； 5、时间复杂度：O(n^2)，for循环嵌套一个while循环； 6、空间复杂度：无限接近于O(logn)——只是在排序那里稍微占了点空间，压栈会占用logn的空间，其他都是只用了有限个变量。

008 四数之和

力扣链接：18. 四数之和

力扣题解链接：排序+双指针解决【四数之和】问题

题目描述：

2.1 题目解析

如下所示——

2.2 思路1：暴力

解法一：暴力求解（会超时）——

大家直接去看上面的【三数之和】：

2.3 思路2：排序 + 双指针

2.3.1 算法思路

1、依次固定一个数a； 2、在这个数a的后面区间上，利用【三数之和】找到三个数，使这三个数的和等于target - a即可，这里注意有两个区间，大的区间里面固定一个数b，小的区间里面定义一个left和right两个下标指针，里面的两数之和，加上a和b，加起来和target比。

2.3.2 代码实现

代码演示——

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        // 创建数组，存放返回值
        vector<vector<int>> ret;
        // 1、排序
        sort(nums.begin(), nums.end());
        // 2、固定i
        int n = nums.size();
        for (int i = 0; i < n;) {
            // 固定j
            for (int j = i + 1; j < n;) {
                // 3、双指针
                int left = j + 1, right = n - 1;
                while (left < right) {
                    // // a >= 0
                    // if (nums[i] > 0)
                    //     break;
                    // // b >= 0
                    // if (nums[j] > 0)
                    //     break;
                    long sum = nums[left] + nums[right];
                    long tmp = nums[i] + nums[j];
                    if (sum > (target - tmp))
                        right--;
                    else if (sum < (target - tmp))
                        left++;
                    else {
                        ret.push_back(
                            {nums[i], nums[j], 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--;
                    }
                }
                // j查重，j移动
                j++;
                while (j < n && nums[j] == nums[j - 1])
                    j++;
            }
            // i查重，i移动
            i++;
            while (i < n && nums[i] == nums[i - 1])
                i++;
        }
        return ret;
    }
};

时间复杂度：O(n^3)，空间复杂度：O(logn)。

2.4 过程推算

本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下！

2.5 反思

1、整体做下来思路正确、逻辑没问题，这一点值得肯定（这里出的岔子就是在a <= 0，b <= 0的判断加上，就报错了）； 2、没有自己独立地想到int类型遇到超级大的数据会怎么样，这里要在定义变量的时候把类型改成long，或者直接临时强制类型转换； 3、吸取了vector<vrctor<int>> ret;和ret.push_back({...});的教训，可以的！