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

《算法竞赛从入门到国奖》算法基础:入门篇-双指针 - 详解

news 2026/5/12 10:00:48

Yupureki:个人主页

✨个人专栏:《C++》《算法》

Yupureki的简介:

前言

双指针有时也被称作滑动窗口，是优化暴力枚举的一种有效方式。
当我们利用两层for循环时，发现可以用两个指针遍历一次，不用回退。即可用双指针来代替两层for循环

1. 唯一的雪花

题目链接:

UVA11572 唯一的雪花 Unique Snowflakes - 洛谷

算法原理

暴力求解:

两层for循环，第一层固定左边的left，第二层从left开始让right一直往右遍历判断。

但是n可能达到10^6的规模，直接超时

双指针:

我们注意到，每次固定好left后，right往后找，最终会找到一个重复的元素。那么在找到重复之前，[left, right]这个区间一定能保证元素不重复。那么找到之后,right也无需往后找了，毕竟这个区间现在非法了，我们让left往后遍历，此时[left，right]仍是非法的，如果left找到了那个与right下标重复的元素，left再++，就能使[left,right]合法了。

因此我们发现如下规律:

right无需往后走，毕竟往后走也是非法的
left往后走的时候,right无需回退，因为我们之前已经维护好[left,right]的信息，保证一定合法。

因此双指针的本质是两个指针无需回退

实操代码

#include 
#include 
#include 
using namespace std;
int main()
{int nums; cin >> nums;while (nums--){int n; cin >> n;vector v;unordered_map m;while (n--){long long num; cin >> num;v.push_back(num);}int left = 0, right = 0;int ret = 0;while (right != v.size()){m[v[right]]++;while (m[v[right]] > 1)//找到了重复的元素m[v[left++]]--;//left向后走if (right - left + 1 > ret)//[left,right]合法后，更新结果ret = right - left + 1;right++;}cout << ret << endl;}return 0;
}

2. 逛画展

题目链接:

P1638 逛画展 - 洛谷

算法原理

这题是要让[left, right]区间内存在1~m的数字

那么我们先让right往后走，每找到一个数字，就往哈希表里存储。当哈希表里面的大小正好为m时，说明[left,right]区间合法。由于我们要"瘦身"区间，即尽量减小[left,right]的长度且合法，那么我们再让left往后走，每找到一个元素，就让哈希表里统计的个数--。直到left所指的这个元素个数正好等于1，就不能走了，因为走了就要违法了。

实操代码

#include 
#include 
#include 
using namespace std;
int main()
{int n, k; cin >> n >> k;vector v;unordered_map m;while (n--){int num; cin >> num;v.push_back(num);}int left = 0, right = 0, ret = 0xffffff;int prev1 = 0, prev2 = 0;while (right != v.size()){m[v[right]]++;while (m.size() == k && m[v[left]] > 1)//缩小区间{m[v[left]]--;if (m[v[left]] == 0)m.erase(v[left]);left++;}if (m.size() == k && right - left + 1 < ret)//更新结果{ret = right - left + 1;prev1 = left;prev2 = right;}right++;}cout << prev1+1 << " " << prev2+1;return 0;
}

3. 字符串

字符串

算法原理

这题跟上题差不多

[left, right]区间保证存在26个小写英文字母
[left,right]尽量小

实操代码

#include 
#include 
#include 
using namespace std;
int main()
{string s;cin>>s;int left = 0,right = 0,ret = 0xffffff;unordered_map m;while(right != s.size()){m[s[right]]++;while(m.size() == 26 && m[s[left]] > 1){m[s[left]]--;if(m[s[left]] == 0)m.erase(s[left]);left++;}if(m.size() == 26 && right - left + 1


4. 丢手绢
题目链接:
丢手绢
算法原理
这题的核心是 几个小朋友围成一个圈
那么在一个圆上，两个小朋友之间有两条路可以走，正好形成了一个圆(其实就是圆上两点)
那么对于这两条圆弧，我们走哪一条?那肯定是较短的那一条，不会有人傻到去走较长的那一条吧
因此，两个小朋友的距离是两条路的较短的那一条
假设从1到5，有从1-2-3-4-5和1-7-6-5两条路，哪条短走哪条
对于临界状态，即两条路正好相等，正好是圆长的一半。因此我们判断，那条路小于等于圆长的一半，就走哪条。
由于我们需要计算两个小朋友，即圆上两点的距离最大值。注意到如果固定left,right向右走，如果[left, right]之间的距离小于等于sum(圆周长)/2，这个是合法情况，找出这个距离的最大值即可。当[left, right]的距离大于sum/2时，我们向右移动left,直到[left, right]合法，更新结果。
因此left 和 right无需回退
实操代码
#include 
#include 
using namespace std;
int main()
{int n; cin >> n;vector v;long long sum = 0;for (int i = 0; i < n; i++){long long num; cin >> num;v.push_back(num);sum += num;}long long left = 0, right = 0, ret = 0;long long k = 0;[left, right]的长度while (right != v.size())//进窗口{k += v[right];while (2 * k >= sum)//长度大于sum/2，出窗口{if (sum - k > ret)ret = sum - k;k -= v[left++];}if (k > ret)//更新结果ret = k;right++;}cout << ret;return 0;
}