算法专题一：双指针算法（下）

书接上回

5.有效三角形个数

力扣： 有效三角形的个数

 在做这道题前我们先讲一个数学知识：已知 a <=  b  <=  c ,此时 a+b>c 可以得出 有效三角形。

所以，我们做这道题时，可以不使用暴力算法。

可以优化为先排序，再用双指针来解决这个问题。

在这里，我们先固定最大的 c 再从 a+b>c 这个条件入手， 如果大于 c 说明我们的 right 大了，所以我们要 right -- ，如果小于 c 说明我们的 left 小了，我们就 left ++。

接下来看代码实现：

class Solution {
public:int triangleNumber(vector<int>& nums) {int sum=0;sort(nums.begin(),nums.end()); // 排序for(int i=nums.size()-1;i>=2;i--){   int left=0;int right=i-1; while(left!=right){if(nums[left]+nums[right]>nums[i]) // 大于 c{sum+=right-left;right--;}else{left++; // 小于c}}}return sum;}
};

 

6.三数之和

力扣：三数之和

这道题让我们解决三数之和的问题。

一看题目，就感觉好像和上一条差不多呀。

只不过我们的条件变成了 a + b = - c 而已，所以我们依然先排序，再用双指针来解决问题。

但再看一眼题目要求，我们还要处理一些细节问题。

去重以及可能会出现数组越界的情况。

代码实现：注意细节

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;// 排序sort(nums.begin(),nums.end());// 双指针解决int n = nums.size();for(int i=0;i<n;){if(nums[i]>0) break; // 小优化int left = i +1,right = n-1, a = -nums[i];while(left<right){int sum = nums[left]+nums[right];if(sum>a) right--;else if (sum<a) left++;else{ret.push_back({nums[i],nums[left],nums[right]});left++,right--;// 去重while(left<right && nums[left]==nums[left-1]) left++;while(left<right && nums[right]==nums[right+1]) right--;}}// 去重 ii++;while(i<n && nums[i] == nums[i-1]) i++;}return ret;}
};

7.四数之和

力扣：四数之和

我们再来看一个题目，四数之和。

没错，就是上一题的变式。

注意解决这条题目之前一定要搞明白上一条题目，那样这道题目就会变得非常简单了。

不信？直接看逻辑，看不懂🪓我。

 

代码实现：看啥看，根据上一题自己改去。