题目
给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
示例 1:文章来源：https://www.toymoban.com/news/detail-643602.html
输入: nums = [2,2,3,4] 输出: 3 解释:有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3
示例 2:文章来源地址https://www.toymoban.com/news/detail-643602.html
输入: nums = [4,2,3,4] 输出: 4
题解
class Solution {
public int triangleNumber(int[] nums) {
Arrays.sort(nums); //对数组排序 增加条件
int ans = 0;
//依次枚举每个元素 定义双指针left和right
//如果nums[left] + nums[right] <= nums[i]则向右移动left
//nums[left]和nums[right]是小的两个数
for (int i = 0; i < nums.length; i++) {
for (int right = i - 1, left = 0; left < right; right--) {
while (left < right && nums[left] + nums[right] <= nums[i]) {
left++;
}
//nums[left] nums[right] nums[i] 符合答案
//第一个元素换成nums[left + 1]...nums[right - 1] 依然符合答案
//所以个数为right-1-left+1=right-left
ans += right - left;
}
}
return ans;
}
}到了这里，关于每日一题 611有效三角形的个数（相向双指针）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
