题目描述

双指针算法解题，边读入边处理双指针，一个循环即可解决

算法1

双指针算法 $O(n)$

C++ 代码

/*
1. 朴素写法： 暴力怎么写———— 即On^2的算法 
2. 然后观察i 和 j两者之间的关系，发现j 不会往后走，j永远向前
3. 所以优化到On
*/
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100050;
int n;
int a[N];
int s[N]; // count 用来计数的数组
int res;
int main()
{
  cin>>n;
  for(int i=0,j=0;i<n;i++)
  {
      cin>>a[i];
      s[a[i]]++;
      while(s[a[i]]>1)
      {
          s[a[j]]--;
          j++;
      }
      res = max(res, i-j+1);
  }

  cout<<res;



  return 0;
}