有效三角形的个数

题目

题目来源：力扣（LeetCode）

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

示例 1:

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

思路分析

排序 + 二分查找

判断三条边能组成三角形的条件为：任意两边之和大于第三边，任意两边之差小于第三边。

我们将三条边进行升序排序，使它们满足 a ≤ b ≤ c，那么 a + c > b 和 b + c > a 是一定成立的，我们只需要保证 a + b > c 。

首先对数组排序。固定最短的两条边，二分查找最后一个小于两边之和的位置。

可以求得固定两条边长之和满足条件的结果。枚举结束后，总和就是答案。

/**
 * @param {number[]} nums
 * @return {number}
 */
var triangleNumber = function (nums) {
  const n = nums.length;
  // 升序排序
  nums.sort((a, b) => a - b);
  let ans = 0;
  // 三条边能组成三角形的条件为：任意两边之和大于第三边，任意两边之差小于第三边
  // 将三条边进行升序排序，使它们满足 a ≤ b ≤ c，那么 a + c > b 和 b + c > a是使一定成立的，我们只需要保证 a + b > c
  for (let i = 0; i < n; ++i) {
    for (let j = i + 1; j < n; ++j) {
      let left = j + 1, right = n - 1, k = j;
      while (left <= right) {
        // 二分查找边c
        const mid = Math.floor((left + right) / 2);
        // nums[i] 为边a 
        // nums[j] 为边b
        // a + b > c
        if (nums[mid] < nums[i] + nums[j]) {
          k = mid;
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
      ans += k - j;
    }
  }
  return ans;
};