给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
示例 1:
输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3示例 2:
输入: nums = [4,2,3,4]
输出: 4提示:
1 <= nums.length <= 10000 <= nums[i] <= 1000
解题思路：排序+双指针
和上一道题一样，如果使用暴力破解也就是枚举的话，此时会超时，所以我们就要换一种方式来解决！
我们首先要知道能构成三角形的条件：两边之和大于第三边。但是因为这道题的数据是无序的，如果我们不用排序的话，可能会稍微麻烦一些，为什么呢，因为我们得判断三条边，两两组合是否都大于第三边才算是构成三角形，这不也和枚举差不多吗？
但是如果我们先进行排序，将数组变成升序序列，这样子有什么好处❓❓❓
这样子就能保证，大的边一定在后边，那我们只需要判断前面两个数是否大于第三个数，如果大于的话，反之用这个第三个数去和前面某一个数组合肯定也是大于另一个数的！这样子的话，我们只需要判断一次，并且不需要全部数据都去枚举！
以下是算法步骤：
- 首先对数组排升序
- 固定最长的一条边，然后运用碰撞指针扫描两条边，大概是这样子：
- 假设最前面的边是
a，中间的边是b，最长的那条边是c。 - 如果
nums[a] + nums[b] ≤ nums[c]的话，说明此时是不构成三角形的，那么我们得让前面的式子增大，也就是让nums[a]增大，所以a++。 - 如果
nums[a] + nums[b] > nums[c]的话，说明构成三角形了，则此时如果b不动，则[a+1, b-1]区间上的元素加上nums[b]也是会大于nums[c]，这是根据排序后的单调性保证的！所以此时的有效组合个数是b-a个组合，并且累加组合数后，继续让b--，看看是否前面还有符合条件的组合！
- 假设最前面的边是
- 扫描完之后，就让最长的一条边的下标
c--，重复上面的操作去计算前面的有效组合！
class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 先排序
int ret = 0;
int c = nums.size() - 1; // 最右边的数
while(c >= 2)
{
int a = 0, b = c - 1;
while(a < b)
{
if(nums[a] + nums[b] <= nums[c])
{
// 无法构成三角形，此时b前面更小的元素肯定也无法构成三角形了，则让a++
a++;
}
else
{
// 可以构成三角形，则让b往前移动看看是否有其它组合
ret += b - a; // 因为此时b不动，[a+1, b-1]区间内的元素加上b肯定也能构成三角形
b--;
}
}
c--;
}
return ret;
}
};