611.有效三角形的个数

链接：611.有效三角形的个数
难度：Medium
标签：贪心、数组、双指针、二分查找、排序
简介：给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。

题解 1 - typescript

• 编辑时间：2021-10-26
• 执行用时：168ms
• 内存消耗：39.8MB
• 编程语言：typescript
• 解法介绍：固定两边长度进行二分。

function triangleNumber(nums: number[]): number {
  const n = nums.length;
  nums.sort((a, b) => a - b);
  let ans = 0;
  for (let i1 = 0; i1 < n - 1; i1++) {
    const num1 = nums[i1];
    for (let i2 = i1 + 1; i2 < n - 1; i2++) {
      const num2 = nums[i2];
      if (num1 + num2 > nums[n - 1]) {
        ans += n - 1 - i2;
        continue;
      }
      let l = i2 + 1;
      let r = n - 1;
      while (l < r) {
        const mid = (l + r) >> 1;
        if (num1 + num2 <= nums[mid]) r = mid;
        else l = mid + 1;
      }
      ans += l - 1 - i2;
    }
  }
  return ans;
}