力扣题目链接[1]
给定一个包含非负整数的数组 nums
,返回其中可以组成三角形三条边的三元组个数。
「示例 1:」
输入: nums = [4,2,3,4]
输出: 4
「提示:」
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
思路:
本题是三数之和的衍生版本。判断三个数是否构成三角形的判断依据是 「两边之和大于第三边」 。
解题的思路是使用 「排序+双指针」 。首先我们要对数组进行排序,确保数组有序可以省去很多不必要的判断。排序后的数组末尾元素就是较大的。我们就依次固定末尾元素,充当三角形的第三条边,然后依次向前进行判断。固定好了第三条边,此时需要在第三条边的范围内分别初始化两条边。第一条边默认是数组第一个元素,第二条边默认是当前第三条边的前一个元素。然后通过判断不断收窄范围。
具体来说,就是在i指针(第一条边)小于j指针(第二条边)的前提下,来判断是否满足构成三角形的条件。如果满足,两个指针之间所有的值(j - i)
都是满足的,同时左移j
指针。如果不满足,则右移i
指针,继续下一迭代判断。
最终累加出来的count
,就是满足的个数,返回即可。
/**
* @param {number[]} nums
* @return {number}
*/
var triangleNumber = function(nums) {
if (!nums || nums.length < 3) return 0; // 如果不满足条件则直接返回0
let count = 0; // 初始化三角形个数
nums.sort((a, b) => a - b); // 排序
for (let k = nums.length - 1; k > 1; k--) { // 固定第三条边
let i = 0; // 初始化第一条边
let j = k - 1; // 初始化第二条边
while(i < j) {
if (nums[i] + nums[j] > nums[k]) { // 满足条件
count += j - i; // 累加所有满足条件的可能
j--; // 左移第二条边
} else {
i++; // 右移第一条边
}
}
}
return count;
};
不管是两数之和还是三数之和,均考查了双指针的思想。采用双指针的前提是要让数据有序,否则无法合理的使用双指针进行求解,这是我们需要特别注意的。
[1]
力扣题目链接: https://leetcode-cn.com/problems/valid-triangle-number/