611. Valid Triangle Number

Difficulty: Medium

Related Topics: Array

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].

Solution

Language: Python3

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        cnt=0
        for k1 in range(len(nums)-2):
            for k2 in range(k1+1,len(nums)-1):
                cnt+=self.findNumberSmallThenN(nums[k1]+nums[k2],nums[k2+1:])
        return cnt
    
    def findNumberSmallThenN(self,n,nums):
        l,r=0,len(nums)-1
        while l<=r:
            mid=l+(r-l)//2
            if nums[mid]>=n:
                r=mid-1
            else:
                l=mid+1
        return r+1