# 611. Valid Triangle Number
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
# Solution
Approach 1: Like 3sum. For each target(longest side), find two smaller sides whose sum > target.
# Code (Python)
Approach 1:
class Solution:
def triangleNumber(self, nums: List[int]) -> int:
# Like 3sum. For each target(longest side), find two smaller sides whose sum > target
nums.sort()
count = 0
for longest_index in range(2, len(nums)):
l, r = 0, longest_index - 1
while l < r:
if nums[l] + nums[r] <= nums[longest_index]:
l += 1
else:
count += (r - l)
r -= 1
return count
# Code (C++)
Approach 1:
Approach 2: