题目
难度:★★★☆☆
类型:平面几何
方法:双指针
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
给定一个包含非负整数的数组,你的任务是统计其中可以组成三角形三条边的三元组个数。
示例 1:
输入: [2,2,3,4]
输出: 3
解释:
有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
注意:
数组长度不超过1000。
数组里整数的范围为 [0, 1000]。
解答
我们一向不主张用暴力法解决枚举类问题。这里介绍一种高效的双指针法。
解决这个问题需要掌握一个小学数学知识:构成三角形的基本条件是,任意两边之和大于第三边,换句话说,较短的两边之和需要大于较长的边。
首先将数组排序,确定最长的边nums[i],在0到i范围内确定另外两条边。使用左右两个指针left,right来标志另外两条短边在数组中的位置,且nums[left] <= nums[right]。满足构成三角形的条件时,即nums[left] + nums[right] > nums[i],说明以i和right为两条长边,以从left到right中所有位置(一共right-left种最短边的情况)为最短边都可以构成三角形,因此计数器增加right-left。否则,最短边的位置右移。
class Solution:
def triangleNumber(self, nums) -> int:
n = len(nums)
counter = 0
nums.sort()
for i in range(2, n):
left, right = 0, i-1
while left < right:
if nums[left] + nums[right] > nums[i]:
counter += right-left
right -= 1
else:
left += 1
return counter
如有疑问或建议,欢迎评论区留言~
有关更多力扣中等题的python解决方案,请移步力扣中等题解析