双指针算法

5.双指针算法

主要思想：

• 针对单一序列使用两个指针，如快速排序
• 针对不同的两个序列使用两个指针，如归并排序

双指针算法可以实现对暴力（朴素）算法的优化，使时间复杂度由O(n^2)优化到O(n)，要求序列有单调关系

代码模板

for(int i=0,j=0;i<n;i++){
    while(j<=i&&check(i,j)) j++;
    //具体逻辑
    .....
}
 

例：给定一个由单词组成的字符串，单词之间用空格相隔，实现输出各个单词

实现思路：使用双指针算法，设置指针i，j，指针i指向单词首部，指针j向后移找到单词之间的空格。输出j和i之间的单词，再让i后移到j的位置，j继续后移找到下一个空格，循环直至j移动到末尾。

#include <iostream>
#include <string>
using namespace std;
 
int main(){
    string str;
    getline(cin,str);//读入空格
    int n=str.length();
    
    for(int i=0;i<n;i++){
 
        int j=i;
        while(j<n&&str[j]!=' ') j++;
        for(int k=i;k<j;k++) cout<<str[k];
        i=j;
    }
    return 0;
    
}
 

AcWing 799.最长连续不重复子序列

实现思路：

• 暴力算法：两重for循环实现所有元素的枚举，选出满足条件的结果
• 双指针算法：设置双指针，指针j指向结果区间的首元素，指针i指向结果的区间的末尾元素。
  • 整数序列用数组a[]存储，设置一个计数数组s[]，s[a[i]]表示元素a[i]出现的次数，最后s[]中为1的元素就是最终结果区间中的元素。
  • j指针首先指向序列首部，i指针不断后移，同时对指向的元素进计数。
  • 当出现某个元素计数值>1，即出现重复时，j指针指向的元素计数要减1，且j指针后移直到此时区间不含重复的数，然后记录当前区间长度，i继续后移判断。循环直到i指针移动到末尾。

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e6+10;
int a[N],s[N];
int n,res=0;
 
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    
    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;
    return 0;
}
 
 

AcWing.800 数组元素的目标和

实现思路：

• 暴力算法，直接两重for循环解决，时间复杂度O(n*m)
• 双指针算法，对于某一个i有一个j满足a[i]+b[j]>=x，且j最小，即为最终的结果。时间复杂度为O(n+m)，因为第二重while循环实际上总共只执行m次(j从m减到0)
• 注意：假如不只一个解，则不能使用这个双指针算法

#include <iostream>
using namespace std;
const int N=1e6+10;
int n,m;
int a[N],b[N];
 
int main(){
    int x;
    cin>>n>>m>>x;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int j=0;j<m;j++) cin>>b[i];
    //双指针算法
    for(int i=0,j=m-1;i<n;i++){
        while(j>=0 && a[i]+b[j]>x) j--;
   		if(a[i]+b[j]==x){
       	 cout>>i>>" ">>j;
         break;
    	} 
   }
    return 0;
}