算法：有效三角形的个数
题目
给定一个包含非负整数的数组，统计其中可以组成三角形三条边的三元组个数。
1. 数组长度不超过1000 2. 数组里整数的范围为 [0, 1000] 输入: [2,2,3,4] 输出: 3 解释: 有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3复制代码
分析
构成三角形的条件：
任意两条边的和大于第三条边，任意两条边的差小于第三条边
1. 暴力循环
暴力的三层循环查找，在每一层的值当做是三角形的一条边，然后再去判断三个值是否满足构成三角形的条件
function getCount (array) {
const L = array.length;
let count = 0;
for(let i = 0; i<L-2; i++) {
// 第一条边
const first = array[i];
for(let m = i + 1; m<L-1; m ++ ) {
// 第二条边
const second = array[m];
for(let n = m+1; n< L; n++) {
// 第三条边
const third = array[n];
// 判断是否满足三角形的条件
if(first + second > third && first + third > second && second + third > first) {
count ++ ;
}
}
}
}
return count;
}复制代码2. 排序 + 双指针
将数组进行从小到大的排序。 固定一条边，另外两条边依次的向右移动。
我们使用一重循环枚举
i。当i固定时，我们使用双指针同时维护j和k，它们的初始值均为i；我们每一次将
j向右移动一个位置，即j + 1，并尝试不断向右移动k，使得k是最大的满足array[k] < array[i] + array[j]，我们将Math.max(k - j, 0)累加。
指针
k不会出现在指针j的右侧，即k - j ≤ 0
function getCount(array) {
const n = array.length;
array.sort((a, b) => a - b);
let count = 0;
for (let i = 0; i < n; ++i) {
let k = i;
for (let j = i + 1; j < n; ++j) {
while (k + 1 < n && array[k + 1] < array[i] + array[j]) {
++k;
}
count += Math.max(k - j, 0);
}
}
return count;
};复制代码结语
作者：forever_Mamba
链接：https://juejin.cn/post/7024327687195852814