【优选算法必刷100题】第005~006题（双指针算法）：有效三角形的个数、查找总价格为目标值的两个商品问题求解

艾莉丝努力练剑

发布于 2025-11-13 11:05:20

390

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

🔥个人主页：艾莉丝努力练剑 ❄专栏传送门：《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题、洛谷刷题、C/C++基础知识知识强化补充、C/C++干货分享&学习过程记录、测试开发要点全知道、Linux操作系统编程详解、笔试/面试常见算法：从基础到进阶 🍉学习方向：C/C++方向学习者 ⭐️人生格言：为天地立心，为生民立命，为往圣继绝学，为万世开太平

005 有效三角形的个数

力扣链接：611. 有效三角形的个数

力扣题解链接：双指针解决【有效三角形的个数】

题目描述：

1.1 思路1：暴力

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

1.1.1 算法思路

三层 for 循环枚举出所有的三元组，并且判断是否能构成三角形。

虽然说是暴力求解，但是还是可以优化一下——

判断三角形的优化：

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

1.1.2 代码实现

代码演示：

//解法一：暴力（会超时）
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;
	}
};

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

1.2 思路2：双指针算法

1.2.1 算法思路

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

1、如果 nums[left] + nums[right] > nums[i]:

（1）说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成比 nums[i] 大的二元组；（2）满足条件的有 right - left 种；（3）此时 right 位置的元素的所有情况相当于全部考虑完毕， right-- ，进入下一轮判断。

2、如果 nums[left] + nums[right]：

（1）说明 left 位置的元素是不可能与 [left + 1, right] 位置上的元素构成满足条件的二元组；（2）left 位置的元素可以舍去， left++ 进入下轮循环。

1.2.2 代码实现

代码演示：

//解法二：双指针算法
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        //1、优化
        sort(nums.begin(), nums.end());
        //2、利用双指针解决
        int sum = 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])
                {
                    sum += right - left;
                    right--;
                }
                else {
                    left++;
                }
            }
        }
        return sum;
    }
};

时间复杂度：O(n^2)，空间复杂度：O(1)。

1.3 过程推算

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

006 查找总价格为目标值的两个商品

力扣链接：LCR 179. 查找总价格为目标值的两个商品

力扣题解链接：双指针解决【查找总价格为目标值的两个商品】

题目描述：

2.1 思路1：暴力

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

2.1.1 算法思路

两层 for 循环列出所有两个数字的组合，判断是否等于目标值。

2.1.2 算法流程

两层 for 循环嵌套——

（1）外层 for 循环依次枚举第一个数 a ；

（2）内层 for 循环依次枚举第二个数 b ，让它与 a 匹配；

ps ：这里有个魔鬼细节：我们挑选第二个数的时候，可以不从第一个数开始选，因为 a 前⾯的数我们都已经在之前考虑过了；因此，我们可以从 a 往后的数开始列举。

（3）然后将挑选的两个数相加，判断是否符合目标值。

2.1.3 代码实现

代码演示：

//解法一：暴力解法（超时）
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 };
    }

时间复杂度：O(n^2)，空间复杂度：O(1)。

2.2 思路2：双指针算法

2.2.1 算法思路

我们注意到本题是升序的数组，因此可以用「对撞指针」优化时间复杂度。

2.2.2 算法流程（附带算法分析，为什么可以使用对撞指针）

1、初始化 left ， right 分别指向数组的左右两端（这里不是我们理解的指针，而是数组的下标）

2、当 left < right 的时候，一直循环——

（1）当 nums[left] + nums[right] == target 时，说明找到结果，记录结果，并且返回；

（2）当 nums[left] + nums[right] < target 时：

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

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

2.2.3 代码实现

代码演示：

//解法二：双指针算法
class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target)
    {
        int left = 0, right = price.size() - 1;
        while (left < right)
        {
            int sum = price[left] + price[right];
            if (sum > target) right--;
            else if (sum < target)left++;
            else return{ price[left],price[right] };
        }
        //照顾编译器
        return{ -1,-1 };
    }
};