611. Valid Triangle Number

给定一堆数字，问用它们能构成多少个三角形。排序后遍历并设i为最长边时，它前面有多少对的和能大于nums[i]。假定当前范围是[l, r]，如果nums[l] + nums[r] > nums[i], 说明最小的l和r都满足，那么l和r之间的也都满足，r无需再遍历, --r；不满足说明l和最大的r都无法构成，那它和任何范围内都无法构成, ++l。

/*
 * @lc app=leetcode id=611 lang=cpp
 *
 * [611] Valid Triangle Number
 *
 * https://leetcode.com/problems/valid-triangle-number/description/
 *
 * algorithms
 * Medium (46.01%)
 * Likes:    672
 * Dislikes: 79
 * Total Accepted:    42.7K
 * Total Submissions: 92.8K
 * Testcase Example:  '[2,2,3,4]'
 *
 * 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:
 * 
 * The length of the given array won't exceed 1000.
 * The integers in the given array are in the range of [0, 1000].
 * 
 * 
 * 
 */
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
         sort(nums.begin(), nums.end());
         int res = 0;
         for (int i = 2; i < nums.size(); ++i) {
             int l = 0, r = i - 1;
             while (l < r) {
                if (nums[l] + nums[r] > nums[i]) {
                    res += r - l;
                    --r;
                } else {
                    ++l;
                }
             }
         }
         return res;
    }
};