每日OJ题_算法_双指针⑤_力扣611. 有效三角形的个数

本文主要是介绍每日OJ题_算法_双指针⑤_力扣611. 有效三角形的个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

力扣611. 有效三角形的个数

解析代码

力扣611. 有效三角形的个数

611. 有效三角形的个数 - 力扣（LeetCode）

难度中等

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

示例 2:

输入: nums = [4,2,3,4]
输出: 4

提示:

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

class Solution {
public:int triangleNumber(vector<int>& nums) {}
};

解析代码

暴力法：（这里代码就不写了，时间复杂度是O（N^3））

三层 for 循环枚举出所有的三元组，并且判断是否能构成三角形。

虽然说是暴力求解，但还是可以优化一下：

如果能构成三角形，需要满足任意两边之和要大于第三边。但是实际上只需让较小的两条边之和大于第三边即可。因此我们可以先将原数组排序，然后从小到大枚举三元组，一方面省去枚举的数量，另一方面方便判断是否能构成三角形。

双指针：时间复杂度是O（N^2）

先将数组排序。根据暴力法中的优化思想，我们可以固定一个“最长边”，然后在比这条边小的有序数组中找出一个二元组，使这个二元组之和大于这个最长边。由于数组是有序的，我们可以利用“对撞指针”来优化。
设最长边枚举到 i 位置，区间 [left，right] 是 i 位置左边的区间（也就是比它小的区间）：

如果 nums[left] + nums[right] > nums[i] ，
说明 [left，right - 1] 区间上的所有元素均可以与 nums[right] 构成比nums[i] 大的二元组，
满足条件的有 right - left 种，此时 right 位置的元素的所有情况相当于全部考虑完毕，减减right ，进入下一轮判断，
如果 nums[left] + nums[right] <= nums[i] ，
说明 left 位置的元素是不可能与 [left + 1，right] 位置上的元素构成满足条件的二元组，此时left 位置的元素可以舍去，加加left 进入下轮循环。

双指针代码：

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(), nums.end());int ret = 0, pos = nums.size() - 1; // 固定的数for(int i = pos; i >= 2; --i) // 因为至少三个数，所以大于等于2{int left = 0, right = i - 1;while(left < right){if(nums[left] + nums[right] > nums[i]){ret += (right - left);--right;}else{++left;}}}return ret;}
};

这篇关于每日OJ题_算法_双指针⑤_力扣611. 有效三角形的个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！