【优选算法】(实战解析双指针的神奇奥秘)

摘要本文介绍了双指针算法的两种常见形式：对撞指针和快慢指针，并详细讲解了它们在数组操作中的应用。对撞指针通过从两端向中间移动解决顺序结构问题，而快慢指针则通过不同速度的移动处理环形结构问题。文章以LeetCode题目为例，展示了双指针算法的实际应用：移动零问题;复写零问题;快乐数问题;盛水最多的容器;有效三角形的个数问题;查找总价格为目标值的两个商品问题;三树之和问题;四数之和问题.通过解决这

承渊政道

510人浏览 · 2026-03-22 11:24:51

承渊政道 · 2026-03-22 11:24:51 发布

🔥承渊政道：个人主页
❄️个人专栏: 《C语言基础语法知识》《数据结构与算法》《C++知识内容》《Linux系统知识》《算法刷题指南》《测评文章活动推广》
✨逆境不吐心中苦,顺境不忘来时路!✨ 🎬 博主简介:

引言:在编程学习的道路上,算法刷题无疑是绕不开的核心环节—它既是检验基础功底的"试金石",也是提升逻辑思维、应对求职面试、突破技术瓶颈的关键路径.但很多学习者都会陷入同样的困境:盲目刷了上百道题,遇到新题目依然无从下手:只会死记硬背题解,换个场景就无法灵活应用;不清楚刷题顺序,在难题中内耗,最终消磨了学习热情,半途而废.事实上,算法刷题从来不是"数量取胜:,而是"方法为王".很多人误以为刷题就是"多做就行",却忽略了背后的逻辑:算法的本质是解决问题的思维模式,刷题的核心目的,是通过刻意练习,掌握不同类型题目的解题思路、拆解技巧,形成自己的解题框架,而非机械记忆代码.无论是编程新手想要夯实基础,还是进阶学习者想要突破瓶颈、冲击大厂面试,一套科学、系统的刷题方法,远比盲目刷题更高效.
为了帮助大家走出刷题误区,少走弯路,我整理了这份算法刷题指南.指南将从刷题规划、算法原理、代码编写等多个维度,结合不同基础学习者的需求,搭建清晰的刷题路径.无论你是刚接触算法的新手,还是已经有一定基础、想要提升效率的学习者,都能在这份指南中找到适合自己的方向,逐步培养算法思维,实现从"会做题"到"会解题"的转变,真正将算法能力内化为自己的核心竞争力.
接下来,就让我们一起开启高效刷题之旅,打破编程壁垒,在算法的世界里稳步前行,解锁更多解题可能.废话不多说下面跟着小编的节奏🎵一起去疯狂的学习吧!

1.双指针背景介绍

常见的双指针有两种形式,一种是对撞指针(左右指针),一种是快慢指针.
对撞指针
一般用于顺序结构中,也称左右指针.
对撞指针从两端向中间移动.一个指针从最左端开始,另一个从最右端开始,然后逐渐往中间逼近.
对撞指针的终止条件一般是两个指针相遇或者错开(也可能在循环内部找到结果直接跳出循环),也就是:

left == right(两个指针指向同一个位置)
left > right(两个指针错开)

快慢指针
又称为龟兔赛跑算法,其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动.
这种方法对于处理环形链表或数组非常有用.其实不单单是环形链表或者是数组,如果我们要研究的问题出现循环往复的情况时,均可考虑使用快慢指针的思想.
快慢指针的实现方式有很多种,最常用的一种就是:
在一次循环中,每次让慢指针(slow)向后移动一位,而快的指针(fast)往后移动两位,实现一快一慢.

算法思路:(快排的思想:数组划分区间-数组分两块➡️双指针算法(这里是利用数组下标充当指针).
在本题中,我们可以用一个 cur 指针从左到右来扫描整个数组,另一个 dest 指针用来记录非零数序列的最后一个位置.根据 cur 在扫描的过程中遇到的不同情况,分类处理,实现数组的划分.此时数组区间被划分成三个:[0,dest] [dest+1,cur-1] [cur,n-1].
在 cur 遍历期间,使 [0, dest] 的元素全部都是非零元素,[dest + 1, cur - 1] 的元素全是零.[cur,n-1] 待处理的区间.
算法流程:
①初始化 cur = 0(用来遍历数组) dest = -1(指向非零元素序列的最后一个位置.因为刚开始我们不知道最后一个非零元素在什么位置,因此初始化为 -1)
②cur 依次往后遍历每个元素,遍历到的元素会有下面两种情况:
(1)遇到的元素是 0 ,cur 直接 ++.因为我们的目标是让 [dest + 1, cur - 1] 内的元素全都是零,因此当 cur 遇到 0 的时候,直接 ++,就可以让 0 在 cur - 1 的位置上,从而在 [dest + 1, cur - 1] 内;
(2)遇到的元素不是 0,dest++,并且交换 cur 位置和 dest 位置的元素,之后让 cur++,扫描下一个元素.

因为 dest 指向的位置是非零元素区间的最后一个位置,如果扫描到一个新的非零元素,那么它的位置应该在 dest + 1 的位置上,因此 dest 先自增 1；
dest++ 之后,指向的元素就是 0 元素(因为非零元素区间末尾的后一个元素就是 0),因此可以交换(swap)到 cur 所处的位置上,实现 [0, dest] 的元素全部都是非零元素,[dest + 1, cur - 1] 的元素全是零.

核心代码

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for(int cur =0,dest=-1;cur<nums.size();cur++)
        if(nums[cur])//处理非零元素
            swap(nums[++dest],nums[cur]);
    }
};

完整测试代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
     void moveZeroes(vector<int>& nums) {
        for(int cur = 0, dest = -1; cur < nums.size(); cur++) {
            if(nums[cur]) { // 处理非零元素
                swap(nums[++dest], nums[cur]);
            }
        }
    }
};

void printVector(const vector<int>& nums) {
    for(int num : nums) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    Solution sol;
    vector<int> nums1 = {0, 1, 0, 3, 12};
    cout << "原数组: ";
    printVector(nums1);
    sol.moveZeroes(nums1);
    cout << "移动后数组: ";
    printVector(nums1);
    cout << endl;
    return 0;
}

3.复写零(OJ题)

算法思路:解法(原地复写➡️双指针(先根据"异地"操作,然后优化双指针下的"就地操作")
如果从前向后进行原地复写操作的话,由于 0 的出现会复写两次,导致没有复写的数被覆盖掉.因此我们选择从后往前的复写策略.
但是从后向前复写的时候,我们需要找到最后一个复写的数,因此我们的大体流程分两步:
先找到最后一个复写的数;
然后从后向前进行复写操作.
算法流程:
①初始化两个指针 cur = 0,dest = -1;
②找到最后一个复写的数:
(1)当 cur < n 的时候,一直执行下面循环:

判断 cur 位置的元素：
- 如果是 0 的话,dest 往后移动两位;
- 否则,dest 往后移动一位.
判断 dest 时候已经到结束位置,如果结束就终止循环;
如果没有结束,cur++,继续判断.

③判断 dest 是否越界到 n 的位置:
(1)如果越界,执行下面三步:
1.n - 1 位置的值修改成 0;
2.cur 向前移动一步;
3.dest 向前移动两步.

④从 cur 位置开始往前遍历原数组,依次还原出复写后的结果数组:
(1)判断 cur 位置的值：
1.如果是0:dest 以及 dest - 1 位置修改成 0,dest -= 2;
2.如果非零:dest 位置修改成 0,dest -= 1;
(2)cur--,复写下一个位置.

核心代码

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        // 1.先找到最后一个数
        int cur = 0, dest = -1, n = arr.size();
        while (cur < n) {
            if (arr[cur])
                dest++;
            else
                dest += 2;
            if (dest >= n - 1)
                break;
            cur++;
        }
        // 2.处理一下边界情况
        if (dest == n) {
            arr[n - 1] = 0;
            cur--;
            dest -= 2;
        }
        // 3.从后向前完成复写操作
        while (cur >= 0) {
            if (arr[cur])
                arr[dest--] = arr[cur--];
            else {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
};

完整测试代码

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        // 1.先找到最后一个数
        int cur = 0, dest = -1, n = arr.size();
        while (cur < n) {
            if (arr[cur])
                dest++;
            else
                dest += 2;
            if (dest >= n - 1)
                break;
            cur++;
        }
        // 2.处理一下边界情况
        if (dest == n) {
            arr[n - 1] = 0;
            cur--;
            dest -= 2;
        }
        // 3.从后向前完成复写操作
        while (cur >= 0) {
            if (arr[cur])
                arr[dest--] = arr[cur--];
            else {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    Solution sol;

    vector<int> arr1 = {1,0,2,3,0,4,5,0};
    cout << "原数组: ";
    printArray(arr1);
    sol.duplicateZeros(arr1);
    cout << "复写后: ";
    printArray(arr1);
    cout << "------------------------" << endl;

    vector<int> arr5 = {0,1};
    cout << "原数组: ";
    printArray(arr5);
    sol.duplicateZeros(arr5);
    cout << "复写后: ";
    printArray(arr5);
    return 0;
}

4.快乐数(OJ题)

题目分析:
为了方便叙述,将对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和这一个操作记为 x 操作；
题目告诉我们,当我们不断重复 x 操作的时候,计算一定会死循环,死的方式有两种:

情况一：一直在 1 中死循环,即 1 -> 1 -> 1 -> 1......
情况二：在历史的数据中死循环,但始终变不到 1

由于上述两种情况只会出现一种,因此,只要我们能确定循环是在情况一中进行,还是在情况二中进行,就能得到结果.

简单证明
前置知识介绍:鸽巢原理(抽屉原理)
鸽巢原理是组合数学中最基础且强大的存在性证明工具,也称为抽屉原理或狄利克雷原理(由德国数学家狄利克雷在1834年正式提出).其核心思想极其朴素:当物品数量超过容器数量时,必然有至少一个容器包含多个物品.
数学公式:若 k > m,则将 k 个元素放入 m 个集合中,至少有一个集合含有≥2 个元素.
示例证明(简单形式):
假设n个抽屉各至多有1个物品,则总物品数≤n,与有n+1个物品矛盾,故至少有一个抽屉有≥2个物品.
有了以上知识我们再来分析这道题
①经过一次变化之后的最大值:9² x10 = 810(2³¹-1=2147483647)选一个更大的最大 9999999999),也就是变化的区间在 [1, 810]之间;
②根据鸽巢原理,一个数变化 811 次之后,必然会形成一个循环;
③因此,变化的过程最终会走到一个圈里面,因此可以用快慢指针来解决.
算法思路(快慢指针)
根据上述的题目分析,我们可以知道,当重复执行 x 的时候,数据会陷入到一个循环之中.
而快慢指针有一个特性,就是在一个圆圈中,快指针总是会追上慢指针的,也就是说他们总会相遇在一个位置上.如果相遇位置的值是1,那么这个数一定是快乐数;如果相遇位置不是1的话,那么就不是快乐数.所以我们定义快慢指针:让慢指针每次向后移动一步,快指针每次向后移动两步.判断相遇时候的值即可.
补充知识:如何求一个数 n 每个位置上的数字的平方和
①把数n每一位的数提取出来：
循环迭代下面步骤：
(1)int m = n % 10 提取个位；
(2)n /= 10 去掉个位；
直到 n 的值变为 0；
②提取每一位的时候,用一个变量 sum 记录这一位的平方与之前提取位数的平方和:sum = sum + m * m

核心代码

class Solution 
{
public:
    int happySum(int n) //返回n这个数每⼀位上的平⽅和
    {
        int sum = 0;
        while (n) 
        {
            int m = n % 10;
            sum += m * m;
            n /= 10;
        }
        return sum;
    }

    bool isHappy(int n) 
    {
        int slow = n, fast = happySum(n);
        while (slow != fast) 
        {
            slow = happySum(slow);
            fast = happySum(happySum(fast));
        }
        return slow == 1;
    }
};

完整测试代码

#include <iostream>
using namespace std;

class Solution
{
public:
    //返回n这个数每一位上的平方和
    int happySum(int n)
    {
        int sum = 0;
        while (n)
        {
            int m = n % 10;  //取最后一位数字
            sum += m * m;    //平方累加
            n /= 10;         //去掉最后一位数字
        }
        return sum;
    }

    //快慢指针判断快乐数
    bool isHappy(int n)
    {
        int slow = n, fast = happySum(n);
        // 快慢指针相遇时退出循环
        while (slow != fast)
        {
            slow = happySum(slow);        //慢指针走一步
            fast = happySum(happySum(fast)); //快指针走两步
        }
        //相遇点为1则是快乐数
        return slow == 1;
    }
};

int main()
{
    Solution sol;

    int num1 = 19;
    cout << num1 << (sol.isHappy(num1) ? " 是快乐数" : " 不是快乐数") << endl;

    int num2 = 1;
    cout << num2 << (sol.isHappy(num2) ? " 是快乐数" : " 不是快乐数") << endl;

    int num3 = 2;
    cout << num3 << (sol.isHappy(num3) ? " 是快乐数" : " 不是快乐数") << endl;

    int num4 = 7;
    cout << num4 << (sol.isHappy(num4) ? " 是快乐数" : " 不是快乐数") << endl;

    int num5 = 10;
    cout << num5 << (sol.isHappy(num5) ? " 是快乐数" : " 不是快乐数") << endl;

    return 0;
}

5.盛最多水的容器(OJ题)

算法思路:解法一(暴力求解➡️会超时)
枚举出能构成的所有容器,找出其中容积最大的值.
容器容积的计算方式：
设两指针 $i$ , $j$ ,分别指向水槽板的最左端以及最右端,此时容器的宽度为 $j - i$ .由于容器的高度由两板中的短板决定,因此可得容积公式：
$\min(\text{height}[i], \text{height}[j])$

核心代码

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int ret = 0;
        // 两层 for 枚举出所有可能出现的情况
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // 计算容积，找出最⼤的那⼀个
                ret = max(ret, min(height[i], height[j]) * (j - i));
            }
        }
        return ret;
    }
};

算法思路:解法二(对撞指针)
设两个指针left,right 分别指向容器的左右两个端点,此时容器的容积:
$(\text{right} - \text{left}) * \min( \text{height}[\text{right}], \text{height}[\text{left}] )$
容器的左边界为 $\text{height}[\text{left}]$ ,右边界为 $\text{height}[\text{right}]$ .
为了方便叙述，我们假设左边边界小于右边边界.
如果此时我们固定一个边界,改变另一个边界,水的容积会有如下变化形式:

容器的宽度一定变小.
由于左边界较小,决定了水的高度.如果改变左边界,新的水面高度不确定,但是一定不会超过右边的柱子高度,因此容器的容积可能会增大.
如果改变右边界,无论右边界移动到哪里,新的水面的高度一定不会超过左边界,也就是不会超过现在的水面高度,但是由于容器的宽度减小,因此容器的容积一定会变小的.

由此可见,左边界和其余边界的组合情况都可以舍去.所以我们可以left++跳过这个边界,继续去判断下一个左右边界.当我们不断重复上述过程,每次都可以舍去大量不必要的枚举过程,直到left与right相遇.期间产生的所有的容积里面的最大值,就是最终答案.这题我们就是利用函数的单调性,使用双指针来解决问题.

核心代码

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1, ret = 0;
        while (left < right) {
            int v = min(height[left], height[right]) * (right - left);
            ret = max(ret, v);
            // 移动指针
            if (height[left] < height[right])
                left++;
            else
                right--;
        }
        return ret;
    }
};

完整测试代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1, ret = 0;
        while (left < right) {
            // 计算当前容积
            int v = min(height[left], height[right]) * (right - left);
            // 更新最大容积
            ret = max(ret, v);
            // 移动短板指针（核心优化逻辑）
            if (height[left] < height[right])
                left++;
            else
                right--;
        }
        return ret;
    }
};


int main() {
    Solution sol;

    vector<int> height1 = {1,8,6,2,5,4,8,3,7};
    cout << "{1,8,6,2,5,4,8,3,7} 最大容积：" << sol.maxArea(height1) << endl;

    vector<int> height2 = {1,1};
    cout << "{1,1} 最大容积：" << sol.maxArea(height2) << endl;

    vector<int> height3 = {4,3,2,1,4};
    cout << "{4,3,2,1,4} 最大容积：" << sol.maxArea(height3) << endl;

    vector<int> height4 = {2,3,4,5,18,17,6};
    cout << "{2,3,4,5,18,17,6} 最大容积：" << sol.maxArea(height4) << endl;

    return 0;
}

6.有效三角形个数(OJ题)

算法思路:解法一(暴力求解➡️会超时)
三层 for 循环枚举出所有的三元组,并且判断是否能构成三角形.
虽然说是暴力求解，但是还是想优化一下：
判断三角形的优化：
如果能构成三角形,需要满足任意两边之和要大于第三边.但是实际上只需让较小的两条边之和大于第三边即可.
因此我们可以先将原数组排序,然后从小到大枚举三元组,一方面省去枚举的数量,另一方面方便判断是否能构成三角形.
核心代码

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        // 1. 排序
        sort(nums.begin(), nums.end());
        int n = nums.size(), ret = 0;
        // 2. 从⼩到⼤枚举所有的三元组
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    // 当最⼩的两个边之和⼤于第三边的时候，统计答案
                    if (nums[i] + nums[j] > nums[k])
                        ret++;
                }
            }
        }
        return ret;
    }
};

算法思路:解法二(排序 + 双指针)
先将数组排序.
根据解法一中的优化思想,我们可以固定一个最长边,然后在比这条边小的有序数组中找出一个二元组,使这个二元组之和大于这个最长边.由于数组是有序的,我们可以利用对撞指针来优化.
设最长边枚举到 i 位置,区间 [left, right] 是 i 位置左边的区间(也就是比它小的区间):

如果 nums[left] + nums[right] > nums[i]：
- 说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成比 nums[i] 大的二元组
- 满足条件的有 right - left 种
- 此时 right 位置的元素的所有情况相当于全部考虑完毕,right--,进入下一轮判断
如果 nums[left] + nums[right] <= nums[i]：
- 说明 left 位置的元素是不可能与 [left + 1, right] 位置上的元素构成满足条件的二元组
- left 位置的元素可以舍去,left++ 进入下轮循环

核心代码

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        //1.优化
        sort(nums.begin(), nums.end());
        //2.利⽤双指针解决问题
        int ret = 0, n = nums.size();
        for (int i = n - 1; i >= 2; i--) //先固定最⼤的数
        {
            //利⽤双指针快速统计符合要求的三元组的个数
            int left = 0, right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    ret += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        return ret;
    }
};

完整测试代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        //1.优化：排序数组
        sort(nums.begin(), nums.end());
        //2.利用双指针解决问题
        int ret = 0, n = nums.size();
        for (int i = n - 1; i >= 2; i--) //先固定最大的数
        {
            //利用双指针快速统计符合要求的三元组的个数
            int left = 0, right = i - 1;
            while (left < right) 
            {
                if (nums[left] + nums[right] > nums[i]) 
                {
                    ret += right - left;
                    right--;
                } 
                else 
                {
                    left++;
                }
            }
        }
        return ret;
    }
};

int main() {
    Solution sol;

    vector<int> nums1 = {2,2,3,4};
    cout << "{2,2,3,4} 有效三角形个数：" << sol.triangleNumber(nums1) << endl;

    vector<int> nums2 = {4,2,3,4};
    cout << "{4,2,3,4} 有效三角形个数：" << sol.triangleNumber(nums2) << endl;

    vector<int> nums3 = {1,2,3};
    cout << "{1,2,3} 有效三角形个数：" << sol.triangleNumber(nums3) << endl;

    vector<int> nums4 = {1,1};
    cout << "{1,1} 有效三角形个数：" << sol.triangleNumber(nums4) << endl;

    return 0;
}

7.查找总价格为目标值的两个商品(OJ题)

算法思路:解法一(暴力解法,会超时)
两层 for 循环列出所有两个数字的组合,判断是否等于目标值.
算法流程:
两层 for 循环：

外层 for 循环依次枚举第一个数 a;
内层 for 循环依次枚举第二个数 b,让它与 a 匹配;
- ps:这里有个细节:我们挑选第二个数的时候,可以不从第一个数开始选,因为 a 前面的数我们都已经在之前考虑过了;因此,我们可以从 a 往后的数开始列举.
然后将挑选的两个数相加,判断是否符合目标值.

核心代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n; i++) 
        { //第⼀层循环从前往后列举第⼀个数
            for (int j = i + 1; j < n;j++) 
            { //第⼆层循环从i位置之后列举第⼆个数
             if (nums[i] + nums[j] ==target) 
             //两个数的和等于⽬标值,说明我们已经找到结果了 
             return {nums[i], nums[j]};
            }
        }
        return {-1, -1};
    }
};

算法思路:解法二(双指针-对撞指针)
注意到本题是升序的数组,因此可以用对撞指针优化时间复杂度.
算法流程(附带算法分析,为什么可以使用对撞指针?)
①初始化 left,right 分别指向数组的左右两端(这里不是我们理解的指针,而是数组的下标)
②当 left < right 的时候,一直循环
(1)当 nums[left] + nums[right] == target 时,说明找到结果,记录结果,并且返回;
(2)当 nums[left] + nums[right] < target 时:

对于 nums[left] 而言,此时 nums[right] 相当于是 nums[left] 能碰到的最大值(别忘了,这里是升序数组哈).如果此时不符合要求,说明在这个数组里面,没有别的数符合 nums[left] 的要求了(最大的数都满足不了你,你已经没救了).因此,我们可以大胆舍去这个数,让 left++,去比较下一组数据;
那对于 nums[right] 而言,由于此时两数之和是小于目标值的,nums[right] 还可以选择比 nums[left] 大的值继续努力达到目标值,因此 right 指针我们按兵不动;

(3)当 nums[left] + nums[right] > target 时,同理我们可以舍去 nums[right](最小的数都满足不了你,你也没救了).让 right--,继续比较下一组数据,而 left 指针不变(因为它还是可以去匹配比 nums[right] 更小的数的).

核心代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum > target)
                right--;
            else if (sum < target)
                left++;
            else
                return {nums[left], nums[right]};
        }
        // 照顾编译器(不然警告我们并不是所有结果都有返回值)
        return {-1, -1};
    }
};

完整测试代码

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum > target)
                right--;
            else if (sum < target)
                left++;
            else
                return {nums[left], nums[right]};
        }
        //处理无结果的情况,避免编译器警告
        return {-1, -1};
    }
};

int main() {
    Solution sol;

    vector<int> nums1 = {2,7,11,15};
    int target1 = 9;
    vector<int> res1 = sol.twoSum(nums1, target1);
    cout << "{2,7,11,15}：找到两个数: " << res1[0] << " 和 " << res1[1] << endl;

    vector<int> nums2 = {2,3,4};
    int target2 = 6;
    vector<int> res2 = sol.twoSum(nums2, target2);
    cout << "{2,3,4}：找到两个数: " << res2[0] << " 和 " << res2[1] << endl;
    
    vector<int> nums3 = {-1,0};
    int target3 = -1;
    vector<int> res3 = sol.twoSum(nums3, target3);
    cout << "{-1,0}：找到两个数: " << res3[0] << " 和 " << res3[1] << endl;

    return 0;
}

8.三数之和(OJ题)

算法思路:解法(排序+双指针)
本题与两数之和类似,是非常经典的面试题.
与两数之和稍微不同的是,题目中要求找到所有不重复的三元组.那我们可以利用在两数之和那里用的双指针思想,来对我们的暴力枚举做优化:
(1)先排序;
(2)然后固定一个数 a;
(3)在这个数后面的区间内,使用双指针算法快速找到两个数之和等于 -a 即可.
但是要注意的是,这道题里面需要有去重操作
找到一个结果之后,left 和 right 指针要跳过重复的元素;
当使用完一次双指针算法之后,固定的 a 也要跳过重复的元素.

核心代码

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;) //固定数 a
        {
            if (nums[i] > 0)
                break; //⼩优化
            int left = i + 1, right = n - 1, target = -nums[i];
            while (left < right) {
                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++;
            while (i < n && nums[i] == nums[i - 1])
                i++;
        }
        return ret;
    }
};

完整测试代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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;) //固定数 a
        {
            if (nums[i] > 0)
                break; //⼩优化
            int left = i + 1, right = n - 1, target = -nums[i];
            while (left < right) {
                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++;
            while (i < n && nums[i] == nums[i - 1])
                i++;
        }
        return ret;
    }
};

void printResult(vector<vector<int>>& res) {
    cout << "[";
    for (int i = 0; i < res.size(); i++) {
        cout << "[";
        for (int j = 0; j < res[i].size(); j++) {
            cout << res[i][j];
            if (j != res[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i != res.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    Solution sol;

    vector<int> nums1 = {-1,0,1,2,-1,-4};
    vector<vector<int>> res1 = sol.threeSum(nums1);
    cout << "{-1,0,1,2,-1,-4} 结果：";
    printResult(res1);

    vector<int> nums2 ={};
    vector<vector<int>> res2 = sol.threeSum(nums2);
    cout << "{} 结果：";
    printResult(res2);

    vector<int> nums3 = {0,0,0};
    vector<vector<int>> res3 = sol.threeSum(nums3);
    cout << "{0,0,0} 结果：";
    printResult(res3);

    vector<int> nums4 = {0,1,1};
    vector<vector<int>> res4 = sol.threeSum(nums4);
    cout << "{0,1,1} 结果：";
    printResult(res4);

    return 0;
}

9.四数之和(OJ题)

算法思路:解法(排序 + 双指针)
①依次固定一个数 a;
②在这个数 a 的后面区间上,利用三数之和找到三个数,使这三个数的和等于 target - a 即可.

核心代码

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        //1.排序
        sort(nums.begin(), nums.end());
        //2.利⽤双指针解决问题
        int n = nums.size();
        for (int i = 0; i < n;) //固定数 a
        {
            //利⽤三数之和
            for (int j = i + 1; j < n;) //固定数 b
            {
                //双指针
                int left = j + 1, right = n - 1;
                long long aim = (long long)target - nums[i] - nums[j];
                while (left < right) {
                    int sum = nums[left] + nums[right];
                    if (sum < aim)
                        left++;
                    else if (sum > aim)
                        right--;
                    else {
                        ret.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--;
                    }
                }
                //去重⼆
                j++;
                while (j < n && nums[j] == nums[j - 1])
                    j++;
            }
            //去重三
            i++;
            while (i < n && nums[i] == nums[i - 1])
                i++;
        }
        return ret;
    }
};

完整测试代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        //1.排序
        sort(nums.begin(), nums.end());
        //2.利⽤双指针解决问题
        int n = nums.size();
        for (int i = 0; i < n;) //固定数 a
        {
            //利⽤三数之和
            for (int j = i + 1; j < n;) //固定数 b
            {
                //双指针
                int left = j + 1, right = n - 1;
                long long aim = (long long)target - nums[i] - nums[j];
                while (left < right) {
                    int sum = nums[left] + nums[right];
                    if (sum < aim)
                        left++;
                    else if (sum > aim)
                        right--;
                    else {
                        ret.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--;
                    }
                }
                //去重⼆
                j++;
                while (j < n && nums[j] == nums[j - 1])
                    j++;
            }
            //去重三
            i++;
            while (i < n && nums[i] == nums[i - 1])
                i++;
        }
        return ret;
    }
};

void printResult(vector<vector<int>>& res) {
    cout << "[";
    for (int i = 0; i < res.size(); i++) {
        cout << "[";
        for (int j = 0; j < res[i].size(); j++) {
            cout << res[i][j];
            if (j != res[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i != res.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    Solution sol;

    vector<int> nums1 = {1,0,-1,0,-2,2};
    int target1 = 0;
    vector<vector<int>> res1 = sol.fourSum(nums1, target1);
    cout << "{1,0,-1,0,-2,2} 结果：";
    printResult(res1);

    vector<int> nums2 = {2,2,2,2,2};
    int target2 = 8;
    vector<vector<int>> res2 = sol.fourSum(nums2, target2);
    cout << "{2,2,2,2,2} 结果：";
    printResult(res2);

    vector<int> nums3 ={};
    int target3 = 0;
    vector<vector<int>> res3 = sol.fourSum(nums3, target3);
    cout << "{} 结果：";
    printResult(res3);

    vector<int> nums4 = {1,2,3};
    int target4 = 6;
    vector<vector<int>> res4 = sol.fourSum(nums4, target4);
    cout << "{1,2,3} 结果：";
    printResult(res4);

    return 0;
}

🚀真正的勇者不是流泪的人,而是含泪奔跑的人!

敬请期待下一篇文章内容:【优选算法】(实战体验滑动窗口的奇妙之旅)

每日心灵鸡汤:苦尽甘来时,再讲来时路!
人的想法和感受,真的会随着时间和认知的改变而改变,原来你笃定不会变的事情,会在之后的某一刻就很容易变得释然.原来你患得患失,整日忧虑不得其解的事情会在之后的某一刻变得不再那么重要.人都是会变得,情绪和感受也都是会流动的,不要把一时的感受定为永恒.时间也不一定能证明什么东西,但一定能让你看透很多人和事.一年的时间也可以让人改变很多,不信你回头去看看去年的自己,也早就不是以前的你自己！
有句话说得很对,成长的经历大概是让人变得越来越安静.一个人的彻悟程度恰等于她所受痛苦的深度.终一天,你会静下来,像个局外人一样回顾自己的往事,笑着摇摇头.保持微笑,苦尽甘来时,再讲来时路!