题目地址：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、 Thelengthofthegivenarraywon'texceed1000.；
2、 Theintegersinthegivenarrayareintherangeof[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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
参考资料： https://leetcode.com/problems/valid-triangle-number/discuss/104174/Java-O(n2)-Time-O(1)-Space
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发