双指针算法

介绍：
双指针应用有多种

• 归并排序应用

• 快速排序应用

y总的模板：

一：例题1

题目测试的时候可以通过acwing随便一个题进行输入输出测试。用ACWINGC测试的时候gets无法通过，不知道网站的编译器有什么问题

题目描述：
实现单词拆分，并且每个单词空格输出
例如：
输入：abc def ghi
输出：
abc
def
ghi

核心思想： 本质就是两个指针分别定位起始和终止，其实位置的指针通过for完成定位，后面指针通过内部的while实现定位，注意每一轮的两个指针的更新。

个人觉得双指针算法的本质就是转换为时间复杂度O(2n)，最终其实就是达到O(n)级别。

#include <iostream>
#include <string.h>
using namespace std;
int main () {
    char a[1000];
    gets(a);
    int n = strlen(a);
    for (int i = 0; i < n; i++) { 
        int j = i; // 每输出一个单词以后就得把j定位到i位置
        while (j < n && a[j] != ' ') j++; // j定位到下一个空格的位置 
        for (int k = i; k < j; k++) cout << a[k]; // 从i到j输出单词
        cout << endl;
        i = j; // i需要更新，for会自动把i从空格位置 + 1
    }
    return 0;
}

二：最长连续不重复子序列

没找到题目，只能在clion上面自己敲。

题目：
从一组数中，找到连续不重复的子序列，计算这个子序列的个数

输入：
5 （数组元素个数）
1 2 3 4 4（数组元素）
输出：
4 （1 2 3 4作为连续不重复的四个数字）

#include <iostream>
using namespace std;
const int N = 100010;
int n;
int s[N], a[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[]数组，判断i到j之间有没有重复元素
        s[a[i]]++; // i指针每向后移动一位的时候，计数数组对应的元素个数就需要加一。
        while (s[a[i]] > 1) {  // 如果s数组这个元素个数大于1,说明i到j区间有重复，有重复了，j就得不断向i靠，消除重复元素
            s[a[j]]--; // 有重复元素，不仅仅j指针需要向后，计数数组也需要去掉j对应的元素
            j++;
        }
        res = max(res, i - j + 1); // 选择最大的
    }
    cout << res << endl;
    return 0;
}