611. Valid Triangle Number 有效三角形的个数

作者： 负雪明烛 id： fuxuemingzhu 个人博客： http://fuxuemingzhu.cn/

---

题目地址：https://leetcode.com/problems/valid-triangle-number/description/

题目描述：

Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are: 
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Note:

1. The length of the given array won't exceed 1000.
2. The integers in the given array are in the range of [0, 1000].

题目大意

给出了一个数组，求在这个数组中能组成多少个三角形。

解题方法

看了下，这个规模是 1000，那么用 O(n^3) 的暴力解法肯定就TLE了。那么只能用更高效的算法。

这个方法是这样的，我们先对这个数组进行排序，排序之后我们来指出这个三角形中最长的边，那么剩下两条边的要求是：两边之和大于最长边。

所以，我们只需要对最长边进行变遍历，对两个短边再遍历即可。短边的遍历方法是：一个从 0 开始的短边 l ，一个从比最长边的短的一个边 r 开始向中间遍历。如果能够成三角形，那么说明比l长的短边和r结合也都能组成三角形。如果不能组成三角形，那么说明l太小了，需要向中间移动。

排序算法时间复杂度是 O(nlogn)，for循环时间复杂度为O(n)，while循环虽然有两个变量，但是这两个变量是同时向中间移动的关系，所以时间复杂度不会超过O(n)。总体的时间复杂度是O(n^2)。空间复杂度是O(1)。

注意，sorted() 函数不是原地排序，如果原地排序需要使用 nums.sort()。这就是我第一次提交失败的地方。

代码如下：

class Solution:
    def triangleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        count = 0
        for i in range(len(nums) - 1, 1, -1):
            l, r = 0, i - 1
            while l < r:
                if nums[l] + nums[r] > nums[i]:
                    count += r - l
                    r -= 1
                else:
                    l += 1
        return count

参考资料： https://leetcode.com/problems/valid-triangle-number/discuss/104174/Java-O(n2)-Time-O(1)-Space

日期

2018 年 9 月 11 日 ———— 天好阴啊