🔥小龙报：个人主页
🎬作者简介：C++研发，嵌入式，机器人，AI等方向学习者
❄️个人专栏：《优选算法》
✨ 永远相信美好的事情即将发生

---

前言

双指针是算法刷题中高效实用的经典解题思想，广泛应用于数组类题型，可有效优化暴力解法、降低时间复杂度。本文聚焦三道LeetCode高频中等难度真题，涵盖盛水容器、有效三角形、两数求和经典题型，深入浅出拆解双指针核心原理、解题逻辑，搭配完整可运行代码，帮助学习者吃透算法技巧，掌握高效刷题思路。

---

一、盛水最多的容器（medium）

1.1题目

链接：盛水最多的容器（medium）

1.2 算法原理

核心思想: 单调性 — 双指针
设两个指针 left ， right 分别指向容器的左右两个端点，此时容器的容积 :
v = (right - left) * min( height[right], height[left]) 容器的左边界为 height[left] ，右边界为 height[right] 。为了方便叙述，我们假设「左边边界」小于「右边边界」。
如果此时我们固定一个边界，改变另一个边界，水的容积会有如下变化形式：
容器的宽度一定变小。
◦ 由于左边界较小，决定了水的高度（木桶效应）。如果改变左边界，新的水面高度不确定，但是一定不会超过右边的柱子高度，因此容器的容积可能会增大。
◦ 如果改变右边界，无论右边界移动到哪里，新的水面的高度一定不会超过左边界，也就是不会超过现在的水面高度，但是由于容器的宽度减小，因此容器的容积一定会变小的。
由此可见，左边界和其余边界的组合情况都可以舍去。所以我们可以 left++ 跳过这个边界，继续去判断下一个左右边界。
当我们不断重复上述过程，每次都可以舍去大量不必要的枚举过程，直到 left 与 right 相遇。期间产生的所有的容积里的最大值，就是最终答案。

1.3 代码

class Solution {
public:
    int maxArea(vector<int>& height) 
    {
        int l = 0,r = height.size() - 1;
        int ret = 0;
        while(l < r)
        {
            int v = min(height[l],height[r]) * (r - l);
            ret = max(ret,v);

            if(height[l] < height[r])
                l++;
            else
                r--;

        } 
        return ret;
    }
};

二、有效三角形的个数

2.1 题目

链接：有效三角形的个数

2.2 算法原理

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

算法思路：
三层 for 循环枚举出所有的三元组，并且判断是否能构成三角形。
虽然说是暴力求解，但是还是想优化⼀下：

判断三角形的优化：
▪ 如果能构成三角形，需要满足任意两边之和要大于第三边。但是实际上只需让较小的两条边之和大于第三边即可。
▪ 因此我们可以先将原数组排序，然后从小到大枚举三元组，一方面省去枚举的数量，另一方面方便判断是否能构成三角形。

2.2.2 解法二

根据「解法一」中的优化思想，我们可以固定⼀个「最长边」，然后在比这条边小的有序数组中找出一个二元组，使这个二元组之和大于这个最长边。由于数组是有序的，我们可以利用「对撞指针」来优化。
设最长边枚举到 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++ 进入下轮循环。

2.3 代码

class Solution 
{
public:
    int triangleNumber(vector<int>& nums) 
    {
        //1.排序
        sort(nums.begin(),nums.end());

        //2.利用双指针 --- a + b > c
        int ret = 0;
        //固定最大边寻找剩下两边
        for(int i = nums.size() - 1;i >= 2;i--)
        {
            int l = 0,r = i - 1;
            while(l < r)
            {
                //固定次大边寻找所有组合
                if(nums[l] + nums[r] > nums[i])
                {
                    ret += r - l;
                    r--;
                }
                else
                    l++;
            } 
        }
        return ret;
    }
};

三、总价格为目标值的商品

3.1 题目

链接：总价格为目标值的商品

3.2 算法原理

算法思路：
注意到本题是升序的数组，因此可以用「对撞指针」优化时间复杂度。
算法流程（附带算法分析，为什么可以使⽤对撞指针）：
a. 初始化 left ， right 分别指向数组的左右两端
b. 当 left < right 的时候，⼀直循环
出现两种情况
i. 当 nums[left] + nums[right] == target 时，说明找到结果，记录结果，并且
返回；
ii. 当 nums[left] + nums[right] < target 时：
• 对于 nums[left] 而言，此时 nums[right] 相当于是 nums[left] 能碰到的
最大值。如果此时不符合要求，说明在这个数组里面，没有别的数符合 nums[left] 的要求了。因此，我们可以打胆舍去这个数，让 left++ ，去比较下一组数据；
• 那对于 nums[right] ，由于此时两数之和是小于目标值的， nums[right]
还可以选择比 nums[left] 大的值继续达到目标值，因此 right 指针我们按
兵不动；
iii. 当 nums[left] + nums[right] > target 时，同理我们可以舍去
nums[right] 。让 right-- ，继续比较下一组组数据，而left 指针不变（因为他还是可以去匹配比较nums[right] 更小的数的）。

3.3 代码

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) 
    {
        int l = 0,r = price.size() - 1;
        while(l < r)
        {
            int sum = price[l] + price[r];
            if(sum < target)
                l++;
            else if(sum > target)
                r--;
            else 
                return {price[l],price[r]};
        }
        return {-1,-1};
    }
};

总结与每日励志

✨本文以三道典型数组算法题为依托，系统讲解了对撞双指针的核心用法，对比暴力解法凸显出该算法高效、简洁的优势，清晰梳理不同题型的解题逻辑与边界条件，配套标准化C++代码便于实操练习。算法学习贵在思考总结与反复刷题，没有一蹴而就的精通，唯有沉下心拆解题型、打磨思路、积累解题经验，持续深耕、持之以恒，才能不断提升编程思维，突破算法学习瓶颈。