给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
image.png
解题思路：
- 最外层i遍历从0至倒数第三位；
- 内层j从i+1开始遍历至倒数第二位；
- 指针k从i+2开始向后游走，直到不满足三角形条件，此时j到k之间的数均满足条件，累加进count；
Python3代码：
class Solution:
def triangleNumber(self, nums: List[int]) -> int:
count = 0
nums.sort()
for i in range(len(nums)-2):
if nums[i] == 0:
continue
k = i+2
for j in range(i+1, len(nums)-1):
while k < len(nums) and nums[i]+nums[j]>nums[k]:
k+=1
count += k-j-1
return count
网友评论