难度: Medium
给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
示例 1:
输入: nums = [2,2,3,4] 输出: 3 解释:有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3
示例 2:
输入: nums = [4,2,3,4] 输出: 4
提示:
1 <= nums.length <= 10000 <= nums[i] <= 1000
Submission
运行时间: 437 ms
内存: 16.0 MB
class Solution:
def triangleNumber(self, nums: List[int]) -> int:
# 三角形 任意两边之和 大于第三边
# 数组有序 c > b > a a+b > c => a+c > b b+c > a
nums.sort()
ans = 0
for k in range(2, len(nums)):
c = nums[k]
a = 0
b = k - 1
while a < b:
if nums[a] + nums[b] > c:
ans += b - a
b = b - 1
else:
a = a + 1
return ans
Explain
这个题解使用了二分查找的思路。首先将数组按升序排序，然后固定最长边 c，用双指针 a 和 b 分别指向最短边和中间边。在 a 和 b 范围内查找符合条件的三角形组合。如果 nums[a] + nums[b] > c，说明存在满足条件的三角形，数量为 b - a，然后将 b 左移缩小范围；否则将 a 右移扩大范围。最后遍历所有可能的最长边 c，将满足条件的三角形数量累加到结果中。
时间复杂度: O(n^2)
空间复杂度: O(1)
class Solution:
def triangleNumber(self, nums: List[int]) -> int:
# 三角形 任意两边之和 大于第三边
# 数组有序 c > b > a a+b > c => a+c > b b+c > a
nums.sort() # 对数组进行升序排序
ans = 0
for k in range(2, len(nums)): # 遍历所有可能的最长边 c
c = nums[k]
a = 0 # 最短边指针
b = k - 1 # 中间边指针
while a < b: # 双指针查找满足条件的三角形
if nums[a] + nums[b] > c: # 找到满足条件的三角形
ans += b - a # 累加满足条件的三角形数量
b = b - 1 # 缩小中间边范围
else:
a = a + 1 # 扩大最短边范围
return ans # 返回满足条件的三角形总数
Explore
对数组进行排序是为了简化三角形合法性的检查过程。排序后，可以保证任意选取的三个数满足 c >= b >= a，这样只需要检查 a + b > c 是否成立即可。此外，排序使得使用双指针策略成为可能，这样可以有效地减少不必要的组合检查，提高算法效率。
是的，该方法通过固定最长边c，并使用双指针a和b（分别指向可能的最短边和中间边），确保了遍历所有可能的三元组组合。双指针从数组的两端向中间移动，能够覆盖所有可能使得 a + b > c 的组合，从而不遗漏任何一个可能的有效三角形。
当 nums[a] + nums[b] > c 时，由于数组已经排序，说明从指针a到指针b-1的任意一个位置 i，nums[i] + nums[b] 都将大于 c（因为 nums[i] >= nums[a]）。因此，对于固定的 b，从 a 到 b-1 的任意位置都可以与 b 形成有效的三角形组合。累加 b - a 是因为这是从 a 到 b-1 的元素个数，即所有满足条件的三元组的数量。
当 nums[a] + nums[b] <= c 时，说明当前最短边 a 太短，无法与 b 组成有效的三角形。因此需要尝试更大的最短边，即将 a 向右移动，以寻找可能存在的有效组合。移动 b（向左移动）将不会帮助增加 nums[a] + nums[b] 的值，反而可能错过一些有效组合。