Leetcode 611 Valid Triangle Number

发表于 |

Valid Triangle Number

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:
The length of the given array won’t exceed 1000.
The integers in the given array are in the range of [0, 1000].

分析：
这道题就是在一个数组内找有多少个三元组满足三个值能构成一个三角形，（大于两边之差，小于两边之和）。 注意，数据长度不超过1000，n^2的方法可行

思路：
先将数组排序，固定前两个值，遍历第三个值，但是不用重复，比如4，5，6，7，8，9，12；第一次固定4，5，第三个值遍历到9结束，然后5变成6，从9遍历到12，中间一定满足故不用重新遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def triangleNumber(nums):
	"""
	:type nums: List[int]
	:rtype: int
	"""
	n = len(nums)
	nums.sort()
	res = 0
	for i in range(n-2):
		k = i+2
		for j in range(i+1,n-1):
			if k == j: k += 1
			while k < n and nums[k] < nums[i] + nums[j]: 
				k += 1
			res += k - (j+1)
	return res


"220 / 220 test cases passed.
difficulty: medium
Runtime: 534 ms"