双指针（5）——有效三角形个数

题目：

这道题我们首先可能会想到暴力解法，三个for循环然后进行check（）。时间复杂度肯定是不允许的。

同时，验证可以组成三角形的条件是任意两边之和大于第三边，这就意味着我们每组要进行三次比较。但也有捷径——只需比较一次即可。但需要条件，让这三个数的组合按从小到大进行排列（a≤b≤c），然后我们只需验证a+b是否大于c即可。因此第一步，我们要把数组进行排序（sort）。

然后我们接下来的思路与双指针（4）的原理有点类似：

我们先计算arr[left]+arr[right](1+9=10,不构成)，如果满足a+b≤c，那么left和right的中间任何一个数和left组合都不能满足三角形,所以此时我们就可以把所有数与left的组合都忽略（不用计算了）即，让left++，这是一次流程。反之如果大于c，那么此次流程中的所有数与right结合都满足要求，则有效三角形个数为right-left，然后让right--进行下一次流程，直到left与right相遇。

注意：以上整个流程都是在与10比较，当二者相遇为一个循环，循环结束后，我们要让二者与9（往前一个）比较。直到走到第三个为止。统计每次循环的有效数并求和。

int Solution(vector<int>& nums)
{sort(nums.begin(),nums.end());int ret=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]){ret+=right-left;right--;}else  left++;}}return ret;}