?

🏝?專欄：?【藍橋杯備篇】
🌅主頁：?f狐o貍x

"今天熬的夜，會變成明天獎狀的閃光點！"

---

目錄

一、唯一的雪花

? ? ? ? 題目鏈接

? ? ? ? 題目描述

? ? ? ? 解題思路

? ? ? ? 解題代碼

二、逛畫展

? ? ? ? 題目鏈接

? ? ? ? 題目描述

? ? ? ? 解題思路

? ? ? ? 解題代碼

三、字符串

? ? ? ? 題目鏈接

? ? ? ? 題目描述

? ? ? ? 解題思路

? ? ? ? 解題代碼

四、丟手絹

? ? ? ? 題目鏈接

? ? ? ? 題目描述

? ? ? ? 解題思路

? ? ? ? 解題代碼

---

????????喵~ 今天要學習的算法是雙指針，也被稱為滑動窗口是?種優化暴?枚舉策略的?段：

? 當我們發現在兩層 for 循環的暴?枚舉過程中，兩個指針是可以不回退的，此時我們就可以利?兩個指針不回退的性質來優化時間復雜度。

一、唯一的雪花

? ? ? ? 題目鏈接

????????UVA11572 唯一的雪花 Unique Snowflakes

? ? ? ? 題目描述

? ? ? ? 解題思路

? ? ? ? 例如題目中給的輸入樣例，我們可以按照以下方法來搞定此題：

? ? ? ? 第一步：先初始化左右指針

? ? ? ? ?第二步：通過右指針向前走開始進窗口

? ? ? ? ?第三步：通過題意判斷出窗口

? ? ? ??第四部：更新結果，重復上述步驟，直到遍歷完全部數組

? ? ? ? 解題代碼

#include <iostream>
#include <unordered_map>using namespace std;typedef long long LL;const int N = 1e6 + 10;int n;
LL a[N];int main()
{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 逛畫展 - 洛谷

? ? ? ? 題目描述

? ? ? ? 解題思路

? ? ? ? 這題其實就是給你一串數字，讓你找到包括所有數字種類的最小子串

? ? ? ? 解題代碼

#include <iostream>using namespace std;const int N = 1e6 + 10;int a[N], mp[N];int n, m;int kind;int main()
{cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];// 初始化int left = 1, right = 1,begin = 1 , ret = n;while (right <= n){// 進窗口if (mp[a[right++]]++ == 0) kind++;// 判斷while (kind == m){// 更新結果int len = right - left ;if (len < ret){ret = len;begin = left;}// 出窗口if (mp[a[left++]]-- == 1) kind--;}}cout << begin << " " << begin + ret - 1 << endl;return 0;
}

三、字符串

? ? ? ? 題目鏈接

????????字符串?

????????題目描述

? ? ? ? 解題思路

? ? ? ? 這題和上一題是一樣的，只是把數字改成字符串了

? ? ? ? 解題代碼

#include <iostream>using namespace std;const int N = 30;int mp[N];
int kind;int main()
{string s; cin >> s;int n = s.size();// 初始化int left = 0, right = 0, ret = n;while(right < n){// 進窗口if(mp[s[right++] - 'a']++ == 0) kind++;// 判斷while(kind == 26){// 更新結果int len = right - left;ret = min(ret, len);// 出窗口if(mp[s[left++] - 'a']-- == 1) kind--;}}cout << ret << endl;return 0;
}

四、丟手絹

? ? ? ? 題目鏈接

????????丟手絹

? ? ? ? 題目描述

? ? ? ? 解題思路

? ? ? ? 這個題依然可以用雙指針來解決，只不過是從一條直線變成了一個環而已

? ? ? ? 解題代碼

#include <iostream>using namespace std;typedef long long LL;const int N = 1e5 + 10;LL a[N];int n;int main()
{cin >> n;LL sum;for(int i = 1; i <= n; i++) {cin >> a[i];sum += a[i];}LL mid = sum / 2;// 初始化LL left = 1, right = 1, ret = 0, len = 0;while(right <= n){// 進窗口if(len <= mid) {len += a[right++];}// 判斷while(len > mid){// 更新結果ret = max(sum - len, ret);// 出窗口len -= a[left++];}if(ret > mid) ret = sum - ret;ret = max(ret, len);}cout << ret << endl;return 0;
}

? ? ? ? 總之，對于雙指針這類型的題目就四步：1. 初始化 2. 進窗口 3. 判斷出窗口 4. 更新結果

? ? ? ??明天我們將學習二分算法，感興趣的朋友記得關注我喲~

? ? ? ? 886~

"今天的bug是明天的經驗值"