class Solution 
{
  public:
    int validTriangleNumber(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());//数组排序
        int n = nums.size();//数组元素个数
        int res = 0;//记录答案
        for (int i = n - 1; i >= 2; i--) //记录三角形最大的一条边
        {
            int left = 0, right = i - 1;
            while (left < right) 
            {
                int sum = nums[left] + nums[right];
                if (sum > nums[i]) 
                {
                    res += right - left;
                    right--;
                } 
                else 
                {
                    left++;
                }
            }
        }
        return res;
    }
};