双指针算法

一、双指针算法两种常见的问题分类：

（1）对于两个序列，维护某种次序，比如归并中合并两个有序序列的操作

（2）对于一个序列，用两个指针维护一段区间

二、核心思想： 朴素算法： for(int i=0;i<n;i++) for(int j=0;j<n;j++) //暴力方式：O(n^2) 双指针算法：

先写一个朴素的算法，寻找 i，j 有没有单调的关系，利用这些单调的关系，将上面的朴素算法算法优化到O(n)

for(i=0,j=0;i<n;i++) { while(j<i&&check(i,j)) j++; //每道题的具体逻辑 //优化到O(n) } 三、双指针的应用： 1. 将字符串“abc def ghi”输出为abc\n def\n ghi

具体实现：

#include<iostream> #include<string.h> using namespace std; int main() { char str[1000]; gets(str); int n=strlen(str); for(int i=0; i<n; i++) { int j=i; while(i<n && str[j] != ' ') j++; //这道题的具体逻辑 for(int k=i;k<j;k++) cout<<str[k]; cout<<endl; i=j; } return 0; 2. 给定一个长度为n的整数序列，请找出最长的不包含重复数字的连续子序列，输出它的长度

//朴素做法：O(n^2) for(int i=0;i<n;i++) for(int j=0;j<=i;j++) if(check(j,i)) { res=max(res,j-i+1); } //双指针算法：O(n) for(int i=0,j=0;i<n;i++) { while(j<=i&&check(j,i)) j++; res=max(res,j-i+1) }

具体实现：

#include<iostream> using namespace std; const int N=100010; int n; int a[N],s[N]; int main() { cin>>n; for(int i=0;i<n;i++) cin>>a[i]; int res=0; for(int i=0,j=0;i<n;i++) { s[a[i]]++; while(s[a[i]]>1) { s[a[j]]--; j++; } res=max(res,i-j+1); } cout<<res<<endl; return 0; }