题目:字符串
题目概述:找包含所有小写字母的最短字符串。
重点思路:
- 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;
}
双指针(滑动窗口)算法的核心思想是:
-
使用两个指针定义窗口边界
-
右指针扩展窗口,收集信息
-
左指针收缩窗口,优化结果
-
通过哈希表高效维护窗口状态
-
在窗口满足条件时更新最终结果