611. 有效三角形的个数
611. 有效三角形的个数
🟠 🔖 贪心
数组
双指针
二分查找
排序
🔗 力扣
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;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
259 | 较小的三数之和 🔒 | [✓] | 数组 双指针 二分查找 1+ | |
2971 | 找到最大周长的多边形 | 贪心 数组 前缀和 1+ |