算法基础学习Day3(双指针)

1.题目

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

2.题目解答

题目及题目解析

算法学习

解法一:暴力枚举

class Solution {
public:int triangleNumber(vector<int>& nums) {int num = 0;std::sort(nums.begin(), nums.end());for (int left = 0; left < nums.size(); left++) {for (int right = left + 1; right < nums.size(); right++) {for (int end = nums.size() - 1; end > right; end--) {if (nums[left] + nums[right] > nums[end]) {num++;}}}}return num;}
};

这里的时间复杂度是NlogN+N*3,虽然能过但是还是可以进行优化的

解法二:利用单调性,使用双指针解决问题

这个优化在排完序的基础上

1. **情况一:**能成为三角形

那么后面从left到right的数都可以组成三角形,直接将这部分的数组进行相加就行

中间的数据个数表达式:right-left

接着让right--

2. **情况二:**不能成为三角形

那么聪right开始到left的数都没办法组成三角形

直接让left++即可

总结来说,步骤如下:

1. 先固定最大的数
2. 用双指针算法快速求解

代码提交

写成代码如下:

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(), nums.end());int ret = 0;for (int i = nums.size() - 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;}
};