611.有效三角形的个数
题目
链接：leetcode链接
思路分析（双指针）
如何构成一个三角形呢？
只需要两边之和大于第三边；
但是，如果已知三条边的大小关系，只需要两条较小边的和大于第三条边即可。
所以，我们需要首先进行排序来获取不同边的大小关系。
我们如何寻找两条较小边和一条大边呢？
不妨先固定一条大边，移动两条小边。
寻找两条小边就需要使用双指针算法。（不妨设大边为target）
设置left和right两个指针，left指向左边，right指向距离大边最近的一条边，依次向中间汇合，进行调整，即可得到答案。
在调整的过程中会遇到两种情况
(1) left + right > target
则，所有left右边的边都可以和right和target构成三角形，
个数位right - left。
right–继续寻找该target下的有效三角形
（2）left + right <= target
则，所有right左边的边都不能喝left和target构成三角形
left++继续寻找该target下的有效三角形。
寻找完所有的大边求和即可。
代码
class Solution {
public:
int triangleNumber(vector<int>& nums) {
int ret = 0;
sort(nums.begin(),nums.end());
for(int i = nums.size() - 1;i >= 2;--i)
{
int left = 0,right = i - 1;
while(left < right)
{
if(nums[left] + nums[right] > nums[i])
{
ret += right - left;
--right;
}
else
{
++left;
}
}
}
return ret;
}
};