05 August 2008
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:
1
2
3
4
5
6
7
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:
找到Array中所有可以组成三角形的triplets，重复数字算不同的triplets（不用去重）。这道题跟3sum指针解法类似，先排序，然后从右向左遍历，两个指针向右和向左移动，满足nums[left]+nums[right] < nums[i]就计数，最后返回。
Time：Arrays.sort()的O(nlogn) + 后面的循环O(n^2) = O(n^2)；Space：每次需要重新创建两个指针，O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public int triangleNumber(int[] nums) {
int result = 0;
if (nums == null || nums.length < 3) {
return result;
}
Arrays.sort(nums);
int len = nums.length;
for (int third = nums.length - 1; third >= 2; third--) { //左边留两个位置
int first = 0, second = third - 1;
while (first < second) {
if (nums[first] + nums[second] > nums[third]) {
result += second - first;//因为排过序了，所以second到first中间的数字都可以和first组成三角形
second--; // 往左移变小一点,成为新的second继续找组合
} else {
//两个较小的数加起来小于或等于第三个数，所以前面两条边应该增大，左边的指针右移
first++;
}
}
}
return result;
}
}