题目：

Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

Input: [2,2,3,4]

Output: 3

Explanation:

Valid combinations are:

2,3,4 (using the first 2)

2,3,4 (using the second 2)

2,2,3

Note:

1. The length of the given array won't exceed 1000.
2. The integers in the given array are in the range of [0, 1000].

分析：

给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。

暴力解决的话可能会超时，我们可以对数组先进行降序排序，这样想一个问题，先选择最大的两个边a，b，如果最小的边c能够和a，b组成三角形，那么比c大的所有边都可以和a，b构成三角形。那么

假定有序数列nums = [9，8，7，6，5，4，3，2]

我们先选择a为9，b为8，c为2，c+b>a三角形成立，而2前面的边均可以和a，b构成三角形，那么此次结果加上(7-1)也就是c的索引减去b的索引，然后在令b为7，也就是下一个元素继续判断。

如果有序数列nums = [9，8，7，6，5，4，3，1]

同样的a为9，b为8，c为1，此时不构成三角形，c的索引减1，也就是判断前一个元素能否和a，b构成三角形，9，8，3成立，所以此次结果加(6-1)，直到a遍历到数组倒数第二个元素为止，因为此时边已经不够了。

程序：

class Solution {

public:

    int triangleNumber(vector<int>& nums) {

        if(nums.size() < ) return ;

        sort(nums.begin(), nums.end(), greater<int>());

        int res = ;

        int n = nums.size();

        for(int a = ; a < n-; ++a){

            int b = a+;

            int c = n-;

            while(b < c){

                if(nums[b] + nums[c] > nums[a]){

                    res = res + c - b;

                    ++b;

                }

                else

                    --c;

            }

        }

        return res;

    }

};