双指针

双指针（Two Pointers）：指的是在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问，从而达到相应的目的。如果两个指针方向相反，则称为「对撞指针」。如果两个指针方向相同，则称为「快慢指针」。如果两个指针分别属于不同的数组 / 链表，则称为「分离双指针」。

在数组的区间问题上，暴力算法的时间复杂度往往是 O(n2)。而双指针利用了区间「单调性」的性质，可以将时间复杂度降到 O(n)。

双指针模版

for(int i = 0,j = 0;i < n;i++) {
		while(i < j && check(i,j)) j++;
  
  	// 每一道题目的具体逻辑
}

双指针经典案例

题目：首先保证输入的字符串每一个单词之间以一个空格隔开，最终我们需要将每一个单词切割出来

思路

我们可以定义两个指针，i指针用来指向每一个单词的头，j指针用来向后移动，最终打印i,j之间的字符，更新起点位置

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    getline(cin,s);
    int n = s.size();
    for(int i = 0;i < n;i++) {
        int j = i;
        while(j < n && s[j] != ' ') j++;
        for(int k = i;k < j;k++) cout << s[k];
        cout << endl;
        i = j;
    }
    return 0;
}

案例二

题目：求最长连续不含重复元素子序列

思路：

我们可以定义两个头结点指针，首先套用模版

for(int i = 0,j = 0;i < n;i++) {
		while(i < j && check(i,j)) j++;
  
  	// 每一道题目的具体逻辑
}

check函数用啦判断i与j之间是否出现了重复元素，如果出现了头j指针向后迁移

逻辑代码部分

ans = max(ans,i - j + 1);

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int a[N],b[N]; //b数组是用来判断是否出现重复元素
int main(){
    int n,ans = 0;
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i];
    
    for(int i = 1,j = 1;i <= n;i++) {
        b[a[i]]++; 
        while(j <= i && b[a[i]] > 1) {
            b[a[j]]--;
            j++;
        }
        
        ans = max(ans,i - j + 1);
    }
    
    cout << ans << endl;
    return 0;
}