Time: 2019-08-08
题目描述
给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
示例 1:
输入: [2,2,3,4]
输出: 3
解释:
有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
注意:
数组长度不超过1000。
数组里整数的范围为 [0, 1000]。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-triangle-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
这是典型的双指针类问题，先排序，然后按照下面的原则判断是否为三角形：
- 最长边的长度小于剩下的两边之和
我们逆序排列数组后，外层主循环表示当前最长的边，然后用两根指针分别指向此最长边下一个元素和数组最右边的元素，开始收缩。
若边界满足，则再向内，一定是都满足，所以，可以更新总数，并left += 1。
若边界不满足，表示两边之和太小，需要right -= 1.
因为：
- left += 1 两边之和减少
- right -= 1 两边之和增大
代码
class Solution:
def triangleNumber(self, nums: List[int]) -> int:
nums.sort(reverse=True)
count = 0
# 外层主循环，直到倒数第三个元素
for i in range(len(nums) - 2):
left = i + 1
right = len(nums) - 1
while left < right:
if nums[i] >= nums[left] + nums[right]: # 不能组成三角形，收缩右边界
right -= 1
else: # 能组成三角形，此时left右移动
count += (right - left)
left += 1
return count
时空复杂度分析
排序时间复杂度：O(nlogn)
for循环内部时间复杂度如何分析？？？
相似题目
TBD.
