題目:字符串
題目概述:找包含所有小寫字母的最短字符串。
重點思路:
- right是 <= len-1
- 字符 - ‘26’轉換成整形再判斷(寫字符a也可以,更準確)。
#include <iostream>
#include <algorithm>
#include <unordered_map>using namespace std;unordered_map<int, int> mp;int main()
{string s; cin >> s;int len = s.size(); int ret = len+1;int left = 0, right = 0, kind = 0;while(right <= len-1){if (mp[s[right]-'26']++ == 0) kind++;while(kind == 26){if (right-left+1 < ret){ret = right-left+1;}if (mp[s[left]-'26']-- == 1) kind--;left++;}right++; }cout << ret << endl;return 0;
}
雙指針(滑動窗口)算法的核心思想是:
-
使用兩個指針定義窗口邊界
-
右指針擴展窗口,收集信息
-
左指針收縮窗口,優化結果
-
通過哈希表高效維護窗口狀態
-
在窗口滿足條件時更新最終結果