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，它们可以作为三角形的三条边，当且仅当：
\begin{cases} a + b > c \\ a + c > b \\ b + c > a \end{cases}
a+b>c
a+c>b
b+c>a
均成立。如果我们将三条边进行升序排序，使它们满足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<nums[i]+nums[j]，我们可以在 [j + 1, n - 1][j+1,n−1] 的下标范围内使用二分查找（其中 n 是数组 nums 的长度），找出最大的满足nums[k]<nums[i]+nums[j] 的下标 k，这样一来，在[j+1,k] 范围内的下标都可以作为边 c 的下标，我们将该范围的长度 k - j累加入答案。
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
