611-ValidTriangleNumber.md

有效三角形的个数

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

示例 1:

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

示例 2:

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

提示:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

思路

1. 排序：首先对输入数组 nums 进行排序。
2. 初始化：定义变量 ans 用于存储可以形成三角形的三元组的数量，初始化为 0。
3. 外层循环：从数组的第三个元素开始（索引为 2），因为至少需要三个元素来形成三角形。变量 i 代表当前考虑的最长边。
4. 内层循环：
   • 初始化 j 为 1，指向第二长边的候选元素。
   • 使用变量 k 从 i - 1 开始递减，k 指向第三边的候选元素。
   • 使用 j 作为左指针，k 作为右指针，当 nums[k] + nums[j]大于 nums[i]时，说明 nums[k]和 nums[j]可以与 nums[i]形成三角形。此时，所有 j 之前的元素（即 j - 1）都可以与 nums[k]形成三角形，因此将 ans 增加 j。
5. 更新指针：如果 nums[k] + nums[j]不大于 nums[i]，则 j 左移一位，继续寻找可以形成三角形的组合。
6. 循环继续：重复步骤 4 和 5，直到 k 递减到 0。
7. 返回结果：返回 ans 作为可以形成三角形的三元组的总数。

时间复杂度：O(n^2)，其中 n 是数组 nums 的长度。这是因为有两层循环，内层循环在最坏情况下会执行 n 次。 空间复杂度：O(1)，只需要常数级别的额外空间。

var triangleNumber = function (nums) {
  nums.sort((a, b) => a - b);
  let ans = 0;
  const n = nums.length;
  for (let i = 2; i < n; ++i) {
    let j = 1;
    for (let k = i - 1; k > 0; --k) {
      while (j > 0 && nums[k] + nums[j] > nums[i]) {
        j--;
      }
      ans += j;
    }
  }
  return ans;
};