★ 算法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;}
};