跳至主要內容

611. 有效三角形的个数


611. 有效三角形的个数open in new window

🟠   🔖  贪心 数组 双指针 二分查找 排序  🔗 力扣open in new window LeetCodeopen in new window

题目

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

题目大意

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

解题思路

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

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

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

  • 对数组从小到大排序,使用 res 记录三元组个数。
  • i = 2 开始遍历数组的每一条边,i 作为最大边。
  • 使用双指针 leftrightleft 指向 0right 指向 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;
};

相关题目

题号标题题解标签难度
259较小的三数之和 🔒open in new window[✓]数组 双指针 二分查找 1+
2971找到最大周长的多边形open in new window贪心 数组 前缀和 1+