双指针算法 cpp

6. 双指针优化暴力枚举又称尺取法/滑动窗口当我们发现在两层 for 循环的暴力枚举过程中两个指针是可以不回退的此时我们就可以利用两个指针不回退的性质来优化时间复杂度因为双指针算法中两个指针是朝着同⼀个⽅向移动的因此也叫做同向双指针学习过程中, 要学会如何从暴力解法优化成双指针算法6.1 唯一的雪花[!洛谷]UVA11572 唯一的雪花 Unique SnowflakesUVA11572 唯一的雪花 Unique Snowflakes - 洛谷题目描述企业家 Emily 有一个很酷的主意把雪花包起来卖。她发明了一台机器这台机器可以捕捉飘落的雪花并把它们一片一片打包进一个包裹里。一旦这个包裹满了它就会被封上送去发售。Emily 的公司的口号是“把独特打包起来”为了实现这一诺言一个包裹里不能有两片一样的雪花。不幸的是这并不容易做到因为实际上通过机器的雪花中有很多是相同的。Emily 想知道这样一个不包含两片一样的雪花的包裹最大能有多大她可以在任何时候启动机器但是一旦机器启动了直到包裹被封上为止所有通过机器的雪花都必须被打包进这个包裹里当然包裹可以在任何时候被封上。输入格式第一行是测试数据组数T TT对于每一组数据第一行是通过机器的雪花总数n nnn ≤ 10 6 n \le {10}^6n≤106下面n nn行每行一个在[ 0 , 10 9 ] [0, {10}^9][0,109]内的整数标记了这片雪花当两片雪花标记相同时这两片雪花是一样的。输出格式对于每一组数据输出最大包裹的大小。输入输出样例 #1输入 #11 5 1 2 3 2 1输出 #13思路:故事背景挖思路:在序列中, 选一段最长连续序列, 这段序列中的所有元素都不同, 输出长度算法原理解法一 : - 会超时暴力枚举 - 枚举出所有符合要求的子数组, 找出最长的枚举所有的子数组 :两层for循环判断枚举的子数组中所有的元素都不同借助哈希表解法二 : 利用调性, 使用 “同向双指针” 来优化性质 : 在暴力枚举的过程中left和right是可以不回退的用法(模板 / 分析方式)初始化 :定义 left 1 , right 1;维护窗口的信息 的结构 : unorderet_mapint , intmp;进窗口 :让 right 所指的元素进窗口mp[a[right]] ;判断 :判断窗口是否合法mp[a[right]] 1出窗口 :(窗口不合法)让left所指的元素出窗口;mp[a[left]]--3-4 循环更新结果 :(窗口合法)ret max(ret , right - left 1);节省时间的原因:规避了很多不必要的枚举过程时间最多为 O(nn) O(2n);代码:#includebits/stdc.husingnamespacestd;constintN1e610;intn;inta[N];intmain(){intT;cinT;while(T--){cinn;for(inti1;in;i)cina[i];//初始化intleft1,right1,ret0;unordered_mapint,intmp;//维护窗口内所有元素出现的次数while(rightn){//进窗口mp[a[right]];while(mp[a[right]]1){//出窗口mp[a[left]]--;left;}//窗口合法 , 更新结果retmax(ret,right-left1);right;}coutretendl;}return0;}数组实现:#includebits/stdc.husingnamespacestd;constintN1e610;intn;inta[N];intmain(){intT;cinT;while(T){cinn;for(inti1;in;i)cina[i];intleft1,right1,ret0;intb[N]{0};while(rightn){b[a[right]];while(b[a[right]]1){b[a[left]]--;left;}retmax(ret,right-left1);right;}coutretendl;}return0;}看到新题, 要尝试用各种解法来解决可以先用暴力枚举的方式写, 然后优化