算法——双指针（day3）
611.有效三角形的个数
611. 有效三角形的个数 - 力扣（LeetCode）
题目解析：
三角形的判定很简单，任意两边之和大于第三边即可。按照正常情况，我们得判断3次才可以确认是否构成三角形。
因为c在本来就是最大的情况下与任意一个数组合只会更大，因此不会再进行判断，这样在数组排序的情况下，我们仅需要判断一次即可~
算法解析：
在这种选择比较大小的组合中往往蕴含着单调性，只要我们找到并利用双指针就可以节省很多时间。
我们先固定最大的数（9）充当c，然后再分别选出两端的数充当a与b（差异大可以更好发现单调性）。当全部选好后无非就是两种结果：
- a+b>c ——构成三角形
- a+b<=c ——不构成三角形
重点来了~我们分别对这两种情况进行分析：
由于是升序排列，那么b(8)就没必要继续与>=a(2)的数进行对比了，直接把b(8)排除，然后往前一位继续对比。
a+b>c—— （有效三角形个数：b-a个，b--)
与上面同理，当我们发现有无法构成的情况时（2与7组合）,2连与该范围最大的7都无法构成，更别提<=b(7)的数了，所以2这种情况也全部排除，然后前进一位继续对比。
a+b<=c——（a++）
最后进行一轮比较完毕后，我们再移动最大数c进行第二轮的比较，以此类推即可。
代码：
class Solution {
public:int triangleNumber(vector<int>& nums) {int n = nums.size();//优化排序sort(nums.begin(), nums.end());int c = n - 1;int sum = 0;//固定最大数while (c >= 2){int a = 0;int b = c - 1;//一轮比较while (a < b){if (nums[a] + nums[b] > nums[c]){//计数sum += (b - a);b--;}else{a++;}}//更换最大数c--;}return sum;}
};179. 查找总价格为目标值的两个商品
题目解析：
这道题相信如果大家有看我们611的题解就会发现很熟悉了，同样的升序，同样的比较大小。用单调性和双指针kuku造就完事了~
算法解析：
最后判断表达式为：
- left+right>t —— right--
- left+right<t —— left++
- left+right==t —— 返回下标
代码：
class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {int n = price.size();int left = 0;int right = n-1;while(left<right){if(price[left]+price[right]>target){right--;}else if(price[left]+price[right]<target){left++;}else{return {price[left],price[right]};}}return {-1,-1};}
};