NO.61十六届蓝桥杯备战|基础算法-双指针|唯一的雪花|逛画展|字符串|丢手绢(C++)

双指针算法有时候也叫尺取法或者滑动窗⼝，是⼀种优化暴⼒枚举策略的⼿段：

• 当我们发现在两层for循环的暴⼒枚举过程中，两个指针是可以不回退的，此时我们就可以利⽤两个指针不回退的性质来优化时间复杂度。
• 因为双指针算法中，两个指针是朝着同⼀个⽅向移动的，因此也叫做同向双指针。
  注意：希望⼤家在学习该算法的时候，不要只是去记忆模板，⼀定要学会如何从暴⼒解法优化成双指针算法。不然往后遇到类似题⽬，你可能压根都想不到⽤双指针去解决。

UVA11572 唯一的雪花 Unique Snowflakes - 洛谷

解法1：暴力枚举：2层for循环
借助哈希表判断枚举的子数组中，所有的元素都不相同
解法2：利用单调性，使用同向双指针来优化
在一个数组中，选择一个最长连续的区域，所有的元素都不相同
当我们「暴⼒枚举」的过程中，固定⼀个起点位置left，然后right之后向后遍历时。当right第
⼀次扫描到⼀个位置，使[left,right]这个区间「出现重复字符」，此时我们会发现：

• right ⽆需再向后遍历，因为继续向后⾛也是「不合法」的；
• left向后移动⼀格之后，right指针也不⽤回退，因为我们已经维护出来[left,right]区间的信息，并且left+1为起点的最优解⼀定不会⽐left为起点的好。
  当我们发现暴⼒枚举的「两个指针不回退」时，就可以⽤「滑动窗⼝」优化：
• 初始化：

left = 1; 
right = 1;
unordered_map<int, int> mp;

• 进窗⼝：right 位置元素记录到统计次数的哈希表中；

mp[a[right]] ++;

• 判断：当哈希表中right 位置的值出现超过1 次之后，窗⼝内⼦串不合法；

mp[a[right]] > 1;

• 出窗⼝：让left 所指位置的元素在哈希表中的次数减⼀；

mp[a[left]] --;

• 更新结果：判断结束之后，窗⼝合法，此时更新窗⼝的⼤⼩

ret = max(ret, right-left+1);

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n;
int a[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T; cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];

        //初始化
        int left = 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;
    } 
    
    return 0;
}

P1638 逛画展 - 洛谷

当我们「暴⼒枚举」的过程中，固定⼀个起点位置left ，然后right之后向后遍历时。当[left,right]第⼀次扫描到⼀个位置，使[left,right]这个区间已经「包含了所有的数时」，此时我们会发现：

• right ⽆需再向后遍历，因为继续向后⾛肯定不是「最优解」；
• left向后移动⼀格之后，right指针也不⽤回退，因为我们已经维护出来[left,right]区间的信息，能够快速得出[left,right]区间「是否合法」，⽽且最「优右端点」铁定不在right左边。
  当我们发现「暴⼒枚举」的两个指针「不回退」时，就可以⽤「滑动窗⼝」优化：
• 初始化

left = 1;
right = 1;
int mp[];
kind = 0;

• 进窗⼝：right位置元素记录到统计次数的哈希表中，如果次数是0变1 ，说明窗⼝内多了「⼀种」字符，记录⼀下；

mp[a[right]]++;
//0->1
kind++

• 判断：当窗⼝内字符种类等于m 时，窗⼝合法，right 停⽌右移，接下来需要出窗⼝；

m == kind;

• 出窗⼝：让left所指位置的元素在哈希表中的次数减⼀，如果次数是1变0 ，说明窗⼝内少了「⼀种」字符，记录⼀下；

mp[a[left]]--;
//1->0
kind--;

• 更新结果：在判断成⽴时，窗⼝合法，此时更新窗⼝的⼤⼩

ret = min(ret, right-left+1);
begin = left;

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10, M = 2e3 + 10;

int n, m;
int a[N];
int kind;
int mp[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int left = 1, right = 1;
    int ret = n, begin = 1;

    while (right <= n)
    {
        //进窗口
        if (mp[a[right]]++ == 0) kind++;
        //判断
        while (kind == m)
        {
            //更新结果
            int len = right-left+1;
            if (len < ret)
            {
                ret = len;
                begin = left;
            }
            //出窗口
            if (mp[a[left]]-- == 1) kind--;
            left++;
        }
        right++;
    }
    cout << begin << " " << begin+ret-1 << endl;
    
    return 0;
}

字符串

当我们「暴⼒枚举」的过程中，固定⼀个起点位置left ，然后right之后向后遍历时。当right第
⼀次扫描到⼀个位置，使[left, right]这个区间已经「包含了所有的⼩写字⺟时」，此时我们会发现：

• right ⽆需再向后遍历，因为继续向后⾛肯定不是「最优解」；
• left向后移动⼀格之后，right指针也不⽤回退，因为我们已经维护出来[left, right]区间的信息，能够快速得出[left+1, right]区间「是否合法」，⽽且最「优右端点」铁定不在right左边。
  当我们发现「暴⼒枚举」的两个指针「不回退」时，就可以⽤「滑动窗⼝」优化：
• 进窗⼝：right位置元素记录到统计次数的哈希表中，如果次数是0变1 ，说明窗⼝内多了「⼀种」字符，记录⼀下；
• 判断：当窗⼝内字符种类等于m 时，窗⼝合法，right 停⽌右移，接下来需要出窗⼝；
• 出窗⼝：让left所指位置的元素在哈希表中的次数减⼀，如果次数是1变0 ，说明窗⼝内少了「⼀种」字符，记录⼀下；
• 更新结果：在判断成⽴时，窗⼝合法，此时更新窗⼝的⼤⼩。

#include <bits/stdc++.h>
using namespace std;

string s;
int mp[26];
int kind;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> s;
    int n = s.size();
    int ret = n;
    
    for (int left = 0, right = 0; right < n; right++)
    {
        //进窗口
        if (mp[s[right] - 'a']++ == 0) kind++;
        //判断
        while (kind == 26)
        {
            //更新结果
            ret = min(ret, right-left+1);
            //出窗口
            if (mp[s[left] - 'a']-- == 1) kind--;
            left++;
        }
    }
    cout << ret << endl;
    
    return 0;
}

丢手绢

分成两段分析
[left, right]以及[right, left]
设left, right区间内的距离是k
right, left的距离是sum-k
其中sum是整个圆圈的长度
当我们「暴⼒枚举」的过程中，固定⼀个起点位置left ，然后right之后向后遍历时，记k为[left, right]之间的距离。当right第⼀次扫描到k x 2 >= sum时，此时我们会发现：

• right ⽆需再向后遍历，因为继续向后⾛的结果⼀定不是最优的；
• left向后移动⼀格之后，right指针也不⽤回退，因为我们已经维护出来[left, right]区间的信息，right回退也不是最优解。
  当我们发现暴⼒枚举的「两个指针不回退」时，就可以⽤「滑动窗⼝」优化：
• 进窗⼝：right 位置与前⼀个位置的距离累加到k 中；
• 判断：k × 2 ≥ sum 时，此时right 指针不⽤前进，应该让left 所指的元素出窗⼝
• 出窗⼝：让left 所指位置与前⼀个位置的距离累减到k 中；
• 更新结果：需要在两个地⽅更新：
  a. 判断结束之后，此时[left, right]之间可能是最优解，⽤k 更新结果；
  b. 判断成⽴的时候，此时[right, left]之间可能是最优解，⽤sum - k更新结果。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
int n;
LL a[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    LL sum = 0;
    for (int i = 1; i <= n; i++) 
    {
        cin >> a[i];
        sum += a[i];
    }
    
    
    int left = 1, right = 1;
    LL k = 0;
    LL ret = 0;
    
    while (right <= n)
    {
        k += a[right];
        while (2 * k >= sum)
        {
            //用sum-k
            ret = max(ret, sum - k);
            k -= a[left++];
        }
        //用k
        ret = max(ret, k);
        right++;
    }
    cout << ret << endl;
    
    return 0;
}