好未来0520上机考试题2：有效三角形的个数

题目

（LeetCode 611.有效三角形的个数）

给定一个包含非负整数的数组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. 对数组进行排序。
2. 固定最短边的位置i（从0到n-3），然后固定第二边j（从i+1到n-2），然后通过二分查找或双指针找到最大的k（j+1开始），使得nums[i] + nums[j] > nums[k]。注意：实际上，我们利用双指针技巧，因为当j增加时，满足条件的k值也会增加（因为数组有序，nums[j]增大，那么nums[i]+nums[j]也增大，所以之前满足的k现在依然满足，且k可以继续向后移动）。
3. 对于每一对(i, j)，我们找到满足条件的最大的k，那么从j+1到k-1（包括j+1到k-1）的所有位置都可以作为第三边，所以有(k- 1 - j)个三角形。

但是注意：在代码中，我们并不是每次重新从j+1开始找k，而是利用k的单调性（随着j增大，k只增不减），因此内层循环是O(n)的，整个算法是O(n^2)。以下是代码实现：

class Solution:def triangleNumber(self, nums: List[int]) -> int:nums.sort()  # 先排序count = 0n = len(nums)for i in range(n - 2):  # 第一个数的索引范围if nums[i] == 0:  # 如果第一个数是0，无法组成三角形continuek = i + 2  # 第三个数的起始位置for j in range(i + 1, n - 1):  # 第二个数的索引范围# 找到最大的k，使得nums[i] + nums[j] > nums[k]while k < n and nums[i] + nums[j] > nums[k]:k += 1# 计算有效三角形数量count += k - j - 1return count