【优选算法系列】【专题一双指针】第三节.611. 有效三角形的个数和LCR 179. 查找总价格为目标值的两个商品

本文主要是介绍【优选算法系列】【专题一双指针】第三节.611. 有效三角形的个数和LCR 179. 查找总价格为目标值的两个商品，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

前言
一、有效三角形的个数
1.1 题目描述
1.2 题目解析
1.2.1 算法原理
1.2.2 代码编写
1.2.3 题目总结
二、查找总价格为目标值的两个商品
2.1 题目描述
2.2 题目解析
2.2.1 算法原理
2.2.2 代码编写
2.2.3 题目总结
总结

前言

一、有效三角形的个数

1.1 题目描述

描述：

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

提示:

1 <= nums.length <= 1000
0 <= nums[i] <= 1000

示例1：

示例2：

1.2 题目解析

1.2.1 算法原理

1.2.2 代码编写

1.2.3 题目总结

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

描述：

购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。

提示：

1 <= price.length <= 10^5
1 <= price[i] <= 10^6
1 <= target <= 2*10^6

示例1：

示例2：

2.2 题目解析

2.2.1 算法原理

解法（双指针 + 对撞指针）：

算法思路：

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

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

步骤a.

初始化 left ， right 分别指向数组的左右两端

（这里不是我们理解的指针，而是数组的下 标）

步骤b.

当 left < right 的时候，一直循环。

情况i. 当 nums[left] + nums[right] == target 时，说明找到结果，记录结果，并且 返回；

情况ii. 当 nums[left] + nums[right] < target 时：

（1）对于 nums[left] 而言，此时 nums[right] 相当于是 nums[left] 能碰到的 最大值。

（别忘了，这里是升序数组哈）。

如果此时不符合要求，说明在这个数组里面， 没有别的数符合 nums[left] 的要求了

（最大的数都满足不了你，你已经没救了）。

因此，我们可以大胆舍去这个left下标的数，让 left++ ，去比较下一组数据；

（2）那对于 nums[right] 而言，由于此时两数之和是小于目标值的， nums[right] 还可以选择比 nums[left] 大的值继续努力达到目标值，因此 right 指针我们按 兵不动；

情况iii.

当 nums[left] + nums[right] > target 时，

同理我们可以舍去 nums[right] （最小的数都满足不了你，你也没救了）。

让 right-- ，继续比较下一 组数据，而left 指针不变

（因为他还是可以去匹配比 nums[right] 更小的数的）。