【Leetcode刷题Python】611. 有效三角形的个数

1 题目

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:

输入: nums = [2,2,3,4] 输出: 3 解释:有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3

2 解析

对于正整数 a, b, ca,b,c，它们可以作为三角形的三条边，当且仅当：

{ a + b > c a + c > b b + c > a \begin{cases} a + b > c \\ a + c > b \\ b + c > a \end{cases} ⎩ ⎨ ⎧​a+b>ca+c>bb+c>a​

a + b > c a + c > b b + c > a a+b>c \\a+c>b \\b+c>a a+b>ca+c>bb+c>a ​ 均成立。如果我们将三条边进行升序排序，使它们满足 a ≤ b ≤ c a ≤ b ≤ c a \leq b \leq c a≤b≤c a≤b≤ca≤b≤c，那么$a+ c > b 和 和 和b + c > a$ 使一定成立的，我们只需要保证 a + b > c。

因此，我们可以将数组nums 进行升序排序，随后使用二重循环枚举 a 和 b。设 a = nums[i], b = nums[j]，为了防止重复统计答案，我们需要保证 i < j。 剩余的边 cc需要满足c