0%

LeetCode611

611. 有效三角形的个数

难度中等230收藏分享切换为英文接收动态反馈

给定一个包含非负整数的数组,你的任务是统计其中可以组成三角形三条边的三元组个数。

示例 1:

1
2
3
4
5
6
7
输入: [2,2,3,4]
输出: 3
解释:
有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

注意:

  1. 数组长度不超过1000。
  2. 数组里整数的范围为 [0, 1000]。

Solution

排序后根据,a+b>c 套两层for循环确定ab,理论上还可以再套一层for循环确定c,但是复杂度太高,达到o(n^3)的复杂度,我们可以通过二分法,找到a+bc的极限值,极限左边都是符合要求的数据,从而n降为lgn的复杂度

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
/**
* @param {number[]} nums
* @return {number}
*/
var triangleNumber = function(nums) {
if (nums.length < 3) return 0;
let ans = 0;
nums = nums.sort();
for (let i = 0; i < nums.length ; i++) {
for (let j = i + 1; j < nums.length ; j++) {
// 二分
let left = j + 1, right = nums.length - 1, k = j;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] < nums[i] + nums[j]) {
k = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
ans += k - j;
}
}
return ans;
};