611.有效三角形的个数
题目解析：
三角形的判定很简单，任意两边之和大于第三边即可。按照正常情况，我们得判断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};
}
};
