#include <iostream> using namespace std; const int N = 100010; int a[N],q[N]; int n, maxl; int main() { scanf("%d",&n); for(int i = 0 ; i < n; i ++) scanf("%d",&a[i]); for(int i = 0 , j = 0;i < n; i ++) { q[a[i]]++; //以a[i]数值为下标,将该下标的元素++ while(j < i && q[a[i]] > 1) q[a[j ++]] --; maxl = max(maxl,i - j + 1); // i - j + 1 i到j之间元素个数包括首尾 // 如果有重复元素了就将指针往后移到i处 } return 0; }
用了双指针算法.
双指针算法可以将O(n2)的朴素算法,利用单调性等规律将时间复杂度优化到O(n),
快排递归都用了双指针算法.
双指针模板
for(int i = 0,j = 0; i < n ; i ++) { while(j < i && check(i,j)) j ++; // 具体逻辑 }
先保证范围合法,再看是否满足条件
原文:https://www.cnblogs.com/sherluoke/p/15013826.html