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

⎩ ⎨ ⎧​a+b>ca+c>bb+c>a​

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

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

3 Python实现

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        
        n = len(nums)
        nums.sort()
        result = 0
        for i in range(n):
            for j in range(i+1,n):
                left,right,k = j+1,n-1,j
                while left<=right:# 注意边界是<=
                    # mid = int((left+right)/2)
                    # 注意使用方法是如下的//
                    mid = (left+right)//2

                    if nums[mid]<nums[i]+nums[j]:
                        k =mid
                        left = mid+1
                    else:
                        right = mid-1
                result +=k-j
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21