★ 算法OJ题 ★ 力扣611 - 有效三角形的个数

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

Ciallo～(∠・ω< )⌒☆ ~ 今天，椎名日和将和大家一起做一道双指针算法题--有效三角形的个数~

一题目

二算法解析

三编写算法

一题目

二算法解析

给三个数，判断是否能构成三角形的条件：两个较小的数相加大于第三个数。

解法⼀：暴力求解

算法思路：三层 for 循环枚举出所有的三元组，并且判断是否能构成三⻆形。（会超时）

此算法时间复杂度为 O(N^3)

若不使用上述原理，则每次需要判断3次，O(3(N^3)) 远大于 O(NlogN + N^3)

class Solution {
public:int triangleNumber(vector<int>& nums) {// 1. 排序sort(nums.begin(), nums.end());int n = nums.size(), ret = 0;// 2. 从⼩到⼤枚举所有的三元组for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {for (int k = j + 1; k < n; k++) {// 当最⼩的两个边之和⼤于第三边的时候，统计答案if (nums[i] + nums[j] > nums[k])ret++;}}}return ret;}
};

解法⼆：排序利用单调性 + 双指针

算法思路：

先将数组排序。
根据解法⼀中的优化思想，我们可以固定最长边，然后在⽐这条边小的有序数组中找两个数，使这个两数之和⼤于这个最⻓边。由于数组是有序的，我们可以利⽤对撞指针来优化。

设最⻓边为C，区间 [left, right] 是 C 位置左边的区间：

nums[left] + nums[right] > C
说明 [left, right - 1] 区间上的所有元素加 nums[right] 都比 C 大
满⾜条件的有 right - left 种
right 位置的元素的所有情况相当于全部考虑完毕， right--

nums[left] + nums[right] <= C
left 位置的元素是不可能与 [left + 1, right] 位置上的元素构成三角形
left++

上述循环完成后C--

三编写算法

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(), nums.end()); // 排序int n = nums.size();int ret = 0; // 符合要求的个数for (int i = n - 1; i >= 2; i--) // 先固定最⼤的数{int left = 0, right = i - 1; // 会跟着循环变化，故须在循环内定义while (left < right) // 利⽤双指针快速统计符合要求的三元组的个数{if(nums[left] + nums[right] > nums[i]){ret += right - left;right--;}else{left++;}}}return ret;}
};