力扣链接：611.有效三角形的个数

难度：⭐⭐

解题关键词：二分查找

解题思路：首先将数组排序，然后用两层循环，第一个指向第一个元素，第二个指向第二个元素，然后在剩下的后面的元素中利用二分查找，找到最后一个满足 first + second > third 的 third 元素，然后这个元素和第二个元素之间的元素就都可以构成三角形。

CAUTION

注意: 这里题目给的是非负数，所以要注意其中元素可能有 0，我们用一个指针停在第二个元素上，然后在二分查找中找到了对应的元素，那就更新，之后它们中间的数字就都可以构成三角形。如果最后指针还停留在第二个元素上，说明 first 等于 0。

function triangleNumber(nums: number[]): number {
  const n = nums.length;

  // 将数组排序
  nums.sort((a, b) => a - b);

  let ans = 0;

  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      // 在前两个元素后面应用二分查找
      let left = j + 1;
      let right = n - 1;
      let k = j;

      while (left <= right) {
        const mid = Math.floor((right - left) / 2) + left;

        // 如果满足两边之和大于第三边，就更新 k
        // 之后 k 和 j 之间的元素都可以构成一个三角形
        if (nums[mid] < nums[i] + nums[j]) {
          k = mid;
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }

      // k 和 j 之间的元素都可以构成一个三角形
      ans += k - j;
    }
  }

  return ans;
}