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

示例 1:

输入: [2,2,3,4]
输出: 3
解释:
有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

注意:

1. 数组长度不超过1000。
2. 数组里整数的范围为 [0, 1000]。

Solution

参考 @ffreturn

• 如何可以构成三角形，其实就是最短的两边之和 a + b > c (c是最长的边)

思路：

1. 排序后我们就能知道哪些是最大和最小边

2. 外循环是最小边a，内循环是中间边b，还有一个是最长边c，这里会不断增加a

   • a的范围是 0~n-2

   • b的范围是 a+1, n-1

3. 如何快速计算组合数量呢

   • 对于当前固定a和固定的b，那么就是不断扩大c直到不满足 a+b > c的条件

   • 此时表示到c范围内的这些数字都是可以满足条件的（记得排除c本身）

// @lc code=start
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        if (nums.size() < 3) return 0;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int res = 0;
        for (int i = 0; i < n-2; ++i) {
            for (int j = i + 1; j < n-1; ++j) {
                int k = j+1;
                while (k < n && nums[i] + nums[j] > nums[k])
                    k++;
                res += (k-j) - 1;
            }
        }
        return res;
    }
};
// @lc code=end