Leetcode 611 有效的三角形个数

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.