有效三角形的个数

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

  • 输入: nums = [2,2,3,4]
    输出: 3
    解释:有效的组合是:
    2,3,4 (使用第一个 2)
    2,3,4 (使用第二个 2)
    2,2,3

  • 输入: nums = [4,2,3,4]
    输出: 4

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
27
var triangleNumber = function(nums) {
    // 数组长度
    const len = nums.length;
    // 升序排序
    nums.sort((a, b) => a - b);
    let res = 0;
    // k是最大的边，从最右边开始
    for (let k = len - 1; k >= 2; k--) {
        // 定义[0,k)内两个指针
        let [left, right] = [0, k - 1];
        while (left < right) {
            if (nums[left] + nums[right] > nums[k]) {
                // 如果当前满足三角形的条件
                // 那么right不动，left右边的各个数+right+k代表的数肯定一定满足
                // 一共有(right-left)个可能，累加到res
                res += right - left;
                // 剩下的都不用判断了，right左移
                right--;
            } else {
                // 当前left不满足条件，太小了，让其大一点
                // left右移
                left++;
            }
        }
    }
    return res;
};