双指针算法+例题

1、性质

• 双指针算法，实质上是把朴素算法O（n^2),发现一些性质，转换成 O（N）时间复杂度。

2、图解+核心思想

3、代码模板 

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

4、例题： AcWing 799. 最长连续不重复子序列 - AcWing

• 题目：

• 给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

  输入格式

  第一行包含整数 n。

  第二行包含 n 个整数（均在 0∼10^5范围内），表示整数序列。

  输出格式

  共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。

  数据范围

  1≤n≤10^5

  输入样例：

  5
  1 2 2 3 5

  输出样例：

  3

• 图解题意：

• 

AC代码： 

#include<iostream>
#include <cmath>

using namespace std;

const int N = 1e5+10;
int a[N],s[N];

int main()
{
    int n,res=0;
    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;
}