class Solution:
    def validTriangleNumber(self , nums: List[int]) -> int:
        nums.sort()
        res = 0
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                left, right = j+1, len(nums)-1
                while left <= right:
                    mid = left + (right - left) // 2
                    if nums[mid] < nums[i] + nums[j]:
                        left = mid + 1
                    else:
                        right = mid - 1
                res += left - (j+1)
        return res