双指针扫描
用于解决一类基于“子段”的统计问题
子段:数组中连续的一段(下标范围可以用一一个闭区间来表示)
这类题目的朴素做法都是两重循环的枚举,枚举左端点l、右端点r (l≤r)
优化手法都是找到枚举中的冗余部分,将其去除
优化策略通常有:
- 固定右端点，看左端点的取值范围
- 例如左端点的取值范围是- -个前缀，可以用“前缀和”等算法维护前缀信息 - 移动一个端点，看另一个端点的变化情况
- 例如一个端点跟随另一个端点单调移动，像一个“滑动窗口”
- 此时可以考虑“双指针扫描”
实战
1.两数之和
https://leetcode.cn/problems/two-sum/
- Hash?
- 排序+双指针扫描?
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<pair<int,int>> pairs; for(int i = 0;i < nums.size();i++){ pairs.push_back({nums[i],i}); } sort(pairs.begin(),pairs.end()); int j = pairs.size() - 1; for(int i = 0;i < pairs.size();i++){ while(i < j && pairs[i].first + pairs[j].first > target) j--; if(i < j && pairs[i].first + pairs[j].first == target) { return {pairs[i].second,pairs[j].second}; } } return {}; } };
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int,int> m; for(int i=0; i<nums.size(); i++){ if(m.find(target-nums[i]) != m.end()) { return {i , m[target-nums[i]]}; } m[nums[i]] = i; } return {}; } };
167.两数之和II -输入有序数组
https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/
class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { int j = numbers.size()-1; for(int i=0; i<numbers.size();i++){ while( i < j && numbers[i] + numbers[j] > target) j--; if( i < j && numbers[i] + numbers[j] ==target){ return {i + 1,j + 1}; } } return {}; } };
class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { // vector<int> ans; // int *slow,fast; // for(int i=0;i<numbers.size()-1;i++) // { // for(int j=i+1;j<numbers.size();j++) // { // if(numbers[i]+numbers[j]==target) // { // return vector<int>{i+1,j+1}; // }else if(numbers[i]+numbers[j]>target) // { // break; // } // } // } // return ans; int l=0,r=numbers.size()-1; while(l<r) { if(numbers[l]+numbers[r]==target) { return vector<int> {l+1,r+1}; }else if(numbers[l]+numbers[r]>target) { r--; }else{ l++; } } return vector<int> {l+1,r+1}; } };
15.三数之和
https://leetcode.cn/problems/3sum/
- 如何避免重复?相同的数不二次枚举
- 如何简化程序实现?模块化!利用“两数之和”
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(),nums.end()); vector<vector<int>> ans; for(int i = 0; i<nums.size(); i++){ if(i>0 && nums[i] == nums[i-1]) continue; vector<vector<int>> jks = twoSum(nums,i + 1, -nums[i]); for(vector<int>& tmp :jks){ ans.push_back({tmp[0],tmp[1],nums[i]}); } } return ans; } private: vector<vector<int>> twoSum(vector<int>& numbers, int start, int target) { vector<vector<int>> ans; int j = numbers.size() - 1; for(int i=start;i < numbers.size();i++){ if(i > start && numbers[i] == numbers[i-1]) continue; while(i < j && numbers[i] + numbers[j] > target) j--; if( i < j && numbers[i] + numbers[j] == target){ ans.push_back({numbers[i],numbers[j]}); } } return ans; } };
11.盛最多水的容器
https://leetcode.cn/problems/container-with-most-water/
解题步骤:
- 两重循环枚举，找冗余
- 发现关键-----盛多少水是由短的那一根决定的，短的算完了就没用了
- 双指针-------两 个指针从头尾向中间移动，每次移动短的那根
class Solution { public: int maxArea(vector<int>& height) { int n=height.size(); int left=0; int right=n-1; int S=0; while(left<right){ S=max((right-left)*min(height[left],height[right]),S); if(height[left]<height[right]) { left++; }else{ right--; } } return S; } };
算法对比
思考:
为什么求"子段和”( 窗口求和)可以用前缀和?
为什么求“滑动窗口最大值”要用单调队列?
遇到一道跟“子段”(窗口)有关的题，什么时候用前缀和,什么时候用双指针扫描，什么时候用单调队列?
区间减法性质
- 指的是[l,r]的信息可以由[1, r]和[1, l- 1]的信息导出
- 满足区间减法，可以用前缀和
维护的信息是关于一个点的，还是一整个候选集合(多个点)的
- 前者用双指针扫描，后者用单调队列
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
