611. Valid Triangle Number
Đề Bài
Given an integer array nums, return 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: nums = [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
Example 2:
Input: nums = [4,2,3,4] Output: 4
Constraints:
1 <= nums.length <= 10000 <= nums[i] <= 1000
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n log n)
💾 Không gian
O(n)
Lời Giải
Python
0611-valid-triangle-number.py
class Solution:
def triangleNumber(self, nums: List[int]) -> int:
n = len(nums)
ans = 0
nums.sort()
for k in range(n):
i = 0
j = k - 1
while i < j:
if nums[i] + nums[j] > nums[k]:
ans += j - i
j -= 1
else:
i += 1
return ans