算法框架
unordered_map 就是哈希表（字典），相当于 Java 的 HashMap，它的一个方法 count(key) 相当于 Java 的 containsKey(key) 可以判断键 key 是否存在。
可以使用方括号访问键对应的值 map[key]。需要注意的是，如果该 key 不存在，C++ 会自动创建这个 key，并把 map[key] 赋值为 0。所以代码中多次出现的 map[key]++ 相当于 Java 的 map.put(key, map.getOrDefault(key, 0) + 1)。
另外，Java 中的 Integer 和 String 这种包装类不能直接用 == 进行相等判断，而应该使用类的 equals 方法。
void slidingWindow(string s, string p) {// ========= 模板：定义相关数据结构，初始化工作============HashMap<Character, Integer> window_map = new HashMap<>();HashMap<Character, Integer> p_map = new HashMap<>();for (int i = 0; i < p.length(); i++){char c1 = p.charAt(i);p_map.put(c1, p_map.getOrDefault(c1, 0) + 1);}int left, right, count;left = right = count = 0;// ================== 模板：开始滑动窗口=====================while (right < s.length()) {// =========== 模板：向右滑动窗口，装填满足的字符到map中==========char c = s.charAt(right);right++;//========== 模板：进行窗口内数据的一系列更新======.../*** debug 输出的位置 ***/System.out.println("left= "+left+" right= "+right+" "+window_map);/********************/// =========== 根据题意：此时“有可能”出现满足条件的解 ==========while (window needs shrink) {// ============= 根据题意：获取“真正”满足条件的解 =============...// ========== 模板：左指针向右滑动，寻找下一个可行解/优化已知解======char d = s.charAt(left);left++;//========== 模板：进行窗口内数据的一系列更新======...}}}
76、最小覆盖子串
滑动窗口算法的思路是这样：
1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。
2、我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。
这个思路其实也不难，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解，也就是最短的覆盖子串。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」这个名字的来历。
1、一开始left和right都在0
2、增加right，知道窗口 [left, right) 包含了 t 中所有字符
3、现在开始增加 left，缩小窗口 [left, right)
4、直到窗口中的字符串不再符合要求，left 不再继续移动
5、之后重复上述过程，先移动 right，再移动 left…… 直到 right 指针到达字符串 S 的末端，算法结束。
//输入"EBBANCF", "ABC"
//输出
0 3
left= 0 right= 1 {}
1 3
left= 0 right= 2 {B=1}
1 3
left= 0 right= 3 {B=2}
2 3
left= 0 right= 4 {A=1, B=2}
2 3
left= 0 right= 5 {A=1, B=2}
3 3
left= 0 right= 6 {A=1, B=2, C=1}
left= 1 right= 6 {A=1, B=2, C=1}
left= 2 right= 6 {A=1, B=1, C=1}
left= 3 right= 6 {A=1, B=0, C=1}
2 3
left= 3 right= 7 {A=1, B=0, C=1}
现在开始套模板，只需要思考以下四个问题：
1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？
如果一个字符进入窗口，应该增加 window 计数器；
2、什么条件下，窗口应该暂停扩大，开始移动 left 缩小窗口？
当 valid 满足 need 时应该收缩窗口；
3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？
如果一个字符将移出窗口的时候，应该减少 window 计数器；
4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
应该在收缩窗口的时候更新最终结果。
public String minWindow(String s, String t) {
//记录t以及滑动窗口window中字符与个数的映射关系
HashMap<Character, Integer> window_map = new HashMap<>();
HashMap<Character, Integer> t_map = new HashMap<>();
for (int i = 0; i < t.length(); i++) {//统计每一个字符的个数
char c1 = t.charAt(i);
t_map.put(c1, t_map.getOrDefault(c1, 0) + 1);
}
//双指针
int left = 0;
int right = 0;
int count = 0;//表示窗口中满足条件的字符个数
//用于更新满足的窗口window的长度，如果len一直是MAX_VALUE, 说明没有满足的子串
int len = Integer.MAX_VALUE;
//用于记录window串的起始位置，则返回s[start, len]
int start = 0;
//增加 right，直到窗口 [left, right) 包含了 t 中所有字符：
while(right < s.length()){
//c 是将移入窗口的字符
char c = s.charAt(right);
//扩大窗口
right++;
//进行窗口内数据的一系列更新
if (t_map.containsKey(c)){//只要c是t种出现的字符就更新
window_map.put(c, window_map.getOrDefault(c, 0) + 1);
//更新c字符出现的次数
if (window_map.get(c).equals(t_map.get(c))){
count++;
}
}
//debug输出的位置
// System.out.println(count+" "+t_map.size());
// System.out.println("left= "+left+" right= "+right+" "+window_map);
//现在开始增加 left，缩小窗口 [left, right)：
//直到窗口中的字符串不再符合要求，left不在移动
while(count == t_map.size()){
//更新并记录window的长度，已经window的起始位置start
if ((right - left) < len){
start = left;
len = right - left;
}
//d是要移出窗口的字符
char d = s.charAt(left);
//缩减窗口
left++;
//如果t_map中包含d
if (t_map.containsKey(d)){
//并且window中d的数量和t_map中d的数量相同
if (window_map.get(d).equals(t_map.get(d))){
//count递减1，因为窗口缩减，d会被移出窗口
count--;
}
//window表中更新数据
window_map.put(d, window_map.get(d) - 1);
}
//debug输出的位置
//System.out.println("left= "+left+" right= "+right+" "+window_map);
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
567. 字符串的排列
现在开始套模板，只需要思考以下四个问题：
1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？
如果一个字符进入窗口，如果t_map包含这个字符则更新window，并判断window和tmap对该字符的个数统计是否相同，如果相同则增加计数器。
2、什么条件下，窗口应该暂停扩大，开始移动 left 缩小窗口？
移动 left 缩小窗口的时机是窗口大小大于 t.size() 时，因为排列嘛，显然长度应该是一样的。当发现 count == t_map.size() 时，就说明窗口中就是一个合法的排列，所以立即返回 true。
3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？
如果一个字符移出窗口，先判断tmap和window对于该字符的个数，如果个数相等则count递减，然后更新window。
4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
应该在收缩窗口时更新结果。
//s1是need，s2是window
public boolean checkInclusion(String s1, String s2) {
HashMap<Character, Integer> window_map = new HashMap<>();
HashMap<Character, Integer> t_map = new HashMap<>();
for (int i = 0; i < s1.length(); i++) {//统计每一个字符的个数
char c1 = s1.charAt(i);
t_map.put(c1, t_map.getOrDefault(c1, 0) + 1);
}
int left = 0, right = 0;
int count = 0;
while (right < s2.length()) {
// c 是将移入窗口的字符
char c = s2.charAt(right);
// 增大窗口
right++;
// 进行窗口内数据的一系列更新
if (t_map.containsKey(c)){
window_map.put(c, window_map.getOrDefault(c, 0) + 1);
if (window_map.get(c).equals(t_map.get(c))){
count++;
}
}
/*** debug 输出的位置 ***/
System.out.println("left= "+left+" right= "+right+" "+window_map);
/********************/
// 判断左侧窗口是否要收缩
while (right - left >= s1.length()) {
//判断是否找到合法的子串
if (count == t_map.size()){
return true;
}
// d 是将移出窗口的字符
char d = s2.charAt(left);
// 缩小窗口
left++;
// 进行窗口内数据的一系列更新
if (t_map.containsKey(d)){
if (window_map.get(d).equals(t_map.get(d))){
count--;
}
window_map.put(d, window_map.getOrDefault(d, 0) - 1);
}
}
}
//未找到符合条件的子串
return false;
}
438. 找到字符串中所有字母异位词
这个所谓的字母异位词，不就是排列吗，搞个高端的说法就能糊弄人了吗？相当于，输入一个串 S，一个串 T，找到 S 中所有 T 的排列，返回它们的起始索引。所以这道题和567这道题，完全一样，只不过返回的是List罢了。
现在开始套模板，只需要思考以下四个问题：
1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？
如果一个字符进入窗口，如果t_map包含这个字符则更新window，并判断window和tmap对该字符的个数统计是否相同，如果相同则增加计数器。
2、什么条件下，窗口应该暂停扩大，开始移动 left 缩小窗口？
移动 left 缩小窗口的时机是窗口大小大于 t.size() 时，因为排列嘛，显然长度应该是一样的。当发现 count == t_map.size() 时，就说明窗口中就是一个合法的排列，所以立即返回 true。
3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？
如果一个字符移出窗口，先判断tmap和window对于该字符的个数，如果个数相等则count递减，然后更新window。
4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
应该在收缩窗口时更新结果。
public boolean checkInclusion(String s1, String s2) {
HashMap<Character, Integer> window_map = new HashMap<>();
HashMap<Character, Integer> t_map = new HashMap<>();
for (int i = 0; i < s1.length(); i++) {//统计每一个字符的个数
char c1 = s1.charAt(i);
t_map.put(c1, t_map.getOrDefault(c1, 0) + 1);
}
int left = 0, right = 0;
int count = 0;
while (right < s2.length()) {
// c 是将移入窗口的字符
char c = s2.charAt(right);
// 增大窗口
right++;
// 进行窗口内数据的一系列更新
if (t_map.containsKey(c)){
window_map.put(c, window_map.getOrDefault(c, 0) + 1);
if (window_map.get(c).equals(t_map.get(c))){
count++;
}
}
/*** debug 输出的位置 ***/
System.out.println("left= "+left+" right= "+right+" "+window_map);
/********************/
// 判断左侧窗口是否要收缩
while (right - left >= s1.length()) {
//判断是否找到合法的子串
if (count == t_map.size()){
return true;
}
// d 是将移出窗口的字符
char d = s2.charAt(left);
// 缩小窗口
left++;
// 进行窗口内数据的一系列更新
if (t_map.containsKey(d)){
if (window_map.get(d).equals(t_map.get(d))){
count--;
}
window_map.put(d, window_map.getOrDefault(d, 0) - 1);
}
}
}
//未找到符合条件的子串
return false;
}
3. 无重复字符的最长子串
这道题没法直接用框架，但是更加简单。
不需要t_map和count，更新窗口内的数据也只需要简单的更新window_map即可。
当window_map.get(c) > 1时，说明窗口内存在重复字符，不符合条件，所以移动left缩小窗口。
需要注意的是，要在收缩窗口之后更新res，因为窗口收缩的 while 条件是存在重复元素，换句话说收缩完成之后一定保证窗口中没有重复。
Your input:"abcabcbb"
Output:3
Expected:3
stdout:
left= 0 right= 1 {a=1}
left= 0 right= 2 {a=1, b=1}
left= 0 right= 3 {a=1, b=1, c=1}
left= 0 right= 4 {a=2, b=1, c=1}
left= 1 right= 5 {a=1, b=2, c=1}
left= 2 right= 6 {a=1, b=1, c=2}
left= 3 right= 7 {a=1, b=2, c=1}
left= 5 right= 8 {a=0, b=2, c=1}
public int lengthOfLongestSubstring(String s) {
// ========= 模板：定义相关数据结构，初始化工作============
HashMap<Character, Integer> window_map = new HashMap<>();
int left, right;
left = right = 0;
//无重复字符的最长子串的长度
int res = 0;
// ================== 模板：开始滑动窗口=====================
while (right < s.length()) {
// =========== 模板：向右滑动窗口，装填满足的字符到map中==========
char c = s.charAt(right);
right++;
//========== 模板：进行窗口内数据的一系列更新======
window_map.put(c, window_map.getOrDefault(c, 0) + 1);
/*** debug 输出的位置 ***/
System.out.println("left= "+left+" right= "+right+" "+window_map);
/********************/
// =========== 根据题意：此时“有可能”出现满足条件的解 ==========
while (window_map.get(c) > 1) {//最长子串，不能含有重复的字符
// ========== 模板：左指针向右滑动，寻找下一个可行解/优化已知解======
char d = s.charAt(left);
left++;
//========== 模板：进行窗口内数据的一系列更新======
window_map.put(d, window_map.getOrDefault(d, 0) - 1);
}
//更新子串的长度
int len = right - left;
res = Math.max(len, res);
}
return res;
}
若有收获，就点个赞吧
0 人点赞
