当前位置：首页 > news >正文

双指针算法 cpp

news 2026/8/27 7:38:14

6. 双指针

优化暴力枚举

又称尺取法/滑动窗口

当我们发现在两层 for 循环的暴力枚举过程中，两个指针是可以不回退的，此时我们就可以利用两个指针不回退的性质来优化时间复杂度

因为双指针算法中，两个指针是朝着同⼀个⽅向移动的，因此也叫做同向双指针

学习过程中, 要学会如何从暴力解法优化成双指针算法

6.1 唯一的雪花

[!洛谷]
UVA11572 唯一的雪花 Unique Snowflakes
UVA11572 唯一的雪花 Unique Snowflakes - 洛谷
题目描述
企业家 Emily 有一个很酷的主意：把雪花包起来卖。她发明了一台机器，这台机器可以捕捉飘落的雪花，并把它们一片一片打包进一个包裹里。一旦这个包裹满了，它就会被封上送去发售。
Emily 的公司的口号是“把独特打包起来”，为了实现这一诺言，一个包裹里不能有两片一样的雪花。不幸的是，这并不容易做到，因为实际上通过机器的雪花中有很多是相同的。Emily 想知道这样一个不包含两片一样的雪花的包裹最大能有多大，她可以在任何时候启动机器，但是一旦机器启动了，直到包裹被封上为止，所有通过机器的雪花都必须被打包进这个包裹里，当然，包裹可以在任何时候被封上。
输入格式
第一行是测试数据组数T TT，对于每一组数据，第一行是通过机器的雪花总数n nn（n ≤ 10 6 n \le {10}^6n≤106），下面n nn行每行一个在[ 0 , 10 9 ] [0, {10}^9][0,109]内的整数，标记了这片雪花，当两片雪花标记相同时，这两片雪花是一样的。
输出格式
对于每一组数据，输出最大包裹的大小。
输入输出样例 #1
输入 #1
1 5 1 2 3 2 1
输出 #1
3

思路:

故事背景挖思路:在序列中, 选一段最长连续序列, 这段序列中的所有元素都不同, 输出长度
算法原理
1. 解法一 : -> 会超时
  暴力枚举 -> 枚举出所有符合要求的子数组, 找出最长的
  1. 枚举所有的子数组 :
    两层for循环
  2. 判断枚举的子数组中所有的元素都不同
    借助哈希表
2. 解法二 : 利用调性, 使用 “同向双指针” 来优化
  1. 性质 : 在暴力枚举的过程中left和right是可以不回退的
  2. 用法(模板 / 分析方式)
    1. 初始化 :
      定义 left = 1 , right = 1;
      维护窗口的信息的结构 : unorderet_map<int , int>mp;
    2. 进窗口 :
      让 right 所指的元素进窗口
      mp[a[right]] ++;
    3. 判断 :
      判断窗口是否合法
      mp[a[right]] > 1
    4. 出窗口 :(窗口不合法)
      让left所指的元素出窗口;
      mp[a[left]]--
    5. 3-4 循环
    6. 更新结果 :(窗口合法)
      ret = max(ret , right - left +1);

节省时间的原因:

规避了很多不必要的枚举过程

时间最多为 O(n+n) = O(2n);

代码:

#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+10;intn;inta[N];intmain(){intT;cin>>T;while(T--){cin>>n;for(inti=1;i<=n;i++)cin>>a[i];//初始化intleft=1,right=1,ret=0;unordered_map<int,int>mp;//维护窗口内所有元素出现的次数while(right<=n){//进窗口mp[a[right]]++;while(mp[a[right]]>1){//出窗口mp[a[left]]--;left++;}//窗口合法 , 更新结果ret=max(ret,right-left+1);right++;}cout<<ret<<endl;}return0;}

数组实现:

#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+10;intn;inta[N];intmain(){intT;cin>>T;while(T){cin>>n;for(inti=1;i<=n;i++)cin>>a[i];intleft=1,right=1,ret=0;intb[N]={0};while(right<=n){b[a[right]]++;while(b[a[right]]>1){b[a[left]]--;left++;}ret=max(ret,right-left+1);right++;}cout<<ret<<endl;}return0;}