有效三角形的个数Java
文章发布较早,内容可能过时,阅读注意甄别。
# 题目
给定一个包含非负整数的数组 nums ,返回其中可以组成三角形三条边的三元组个数。
示例 1:
输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
示例 2:
输入: nums = [4,2,3,4]
输出: 4
提示:
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 1000
# 思路
O(n2)方法,改进方式是将第二层和第三层循环合成一个,从后往前遍历可以提前结束循环
# 解法
class Solution {
// O(n2)方法,改进方式是将第二层和第三层循环合成一个,从后往前遍历可以提前结束循环
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int result = 0;
for (int i = nums.length - 1; i >= 2; i--) {
int k = 0;
int j = i - 1;
while (k < j) {
//满足该条件,说明从num[k]到num[j]的数都满足要求,结果直接加上j - k
if (nums[k] + nums[j] > nums[i]) {
result += j - k;
j--;
} else {
//否则k自增,重新判断
k++;
}
}
}
return result;
}
}
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
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
# 总结
- 分析出几种情况,然后分别对各个情况实现