首页 > Windows开发 > 详细

AcWING 799. 最长连续不重复子序列

时间:2021-07-15 11:53:07      阅读:19      评论:0      收藏:0      [点我收藏+]

#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 ++;
    
    // 具体逻辑
    
}

先保证范围合法,再看是否满足条件

AcWING 799. 最长连续不重复子序列

原文:https://www.cnblogs.com/sherluoke/p/15013826.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!