611. Valid Triangle Number

🟠   🔖  贪心 数组 双指针 二分查找 排序  🔗 LeetCode

题目

Given an integer array nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

Input: nums = [2,2,3,4]

Output: 3

Explanation: Valid combinations are:

2,3,4 (using the first 2)

2,3,4 (using the second 2)

2,2,3

Example 2:

Input: nums = [4,2,3,4]

Output: 4

Constraints:

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

题目大意

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

解题思路

构成三角形的条件为：任意两边和大于第三边，或者任意两边差小于第三边。只要满足这两个条件之一就可以构成三角形。以任意两边和大于第三边为例，如果用 a、b、c 来表示的话，应该同时满足 a + b > c、a + c > b、b + c > a。如果我们将三条边升序排序，假设 a <= b <= c，则如果满足 a + b > c，则 a + c > b 和 b + c > a 一定成立。

所以我们可以先对 nums 进行排序。然后固定最大边 i，利用对撞指针 left、right 查找较小的两条边。然后判断是否构成三角形并统计三元组个数。

为了避免重复计算和漏解，要严格保证三条边的序号关系为：left < right < i。具体做法如下：

• 对数组从小到大排序，使用 res 记录三元组个数。
• 从 i = 2 开始遍历数组的每一条边，i 作为最大边。
• 使用双指针 left、right。left 指向 0，right 指向 i - 1。
  • 如果 nums[left] + nums[right] <= nums[i]，说明第一条边太短了，可以增加第一条边长度，所以将 left 右移，即 left += 1。
  • 如果 nums[left] + nums[right] > nums[i]，说明可以构成三角形，并且第二条边固定为 right 边的话，第一条边可以在 [left, right - 1] 中任意选择。所以三元组个数要加上 right - left。即 res += (right - left)。
• 直到 left == right 跳出循环，输出三元组个数 res。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var triangleNumber = function (nums) {
  nums = nums.sort((a, b) => a - b);
  let res = 0;
  for (let i = nums.length - 1; i > 1; i--) {
    let left = 0;
    let right = i - 1;
    while (left < right) {
      if (nums[left] + nums[right] <= nums[i]) {
        left++;
      } else {
        res += right - left;
        right--;
      }
    }
  }
  return res;
};

相关题目

相关题目

• 🔒 3Sum Smaller

- [🔒 3Sum Smaller](https://leetcode.com/problems/3sum-smaller)