算法Day06-算法研习指导之滑动窗口

野性酷女 2022-11-26 07:50 108阅读 0赞

### 滑动窗口 ###

*  基本概念
 *  最小覆盖子串
 *  字母异位词
 *  无重复字符的最长子串
 *  滑动窗口技巧总结

# 基本概念 #

*  **滑动窗口:** 是高级双指针技巧的算法框架,涉及字符串匹配问题
 *  **滑动窗口使用的数据结构:**
    
     *  **unordered\_map :** 哈希表
        
         *  包含一个方法**count(key),** 相当于**containsKey(key).** 可以判断**key**是否存在
     *  **map\[key\] :**
        
         *  可以使用方括号访问键对应的值**map\[key\].** 需要注意,如果该**key**不存在,会自动创建这个**key,** 并且将**map\[key\]** 赋值为**0**
         *  **map\[key\]++** 相当于**Java**的**map.put(key, map.getOrDefault(key, 0) + 1)**

# 最小覆盖子串 #

*  **题目:** 要在**S(source)** 中找到包含**T(target)** 中全部字母的一个子串,这个子串一定要是所有子串中最短的
 *  **直接法求解的代码:**

for (int i = 0; i < s.size(); i++):
    	for (int j = i + 1; j < s.size(); j++):
    		if s[i : j] 包含 t 的所有字母:
    			更新结果

*  思路简单直接,但是这个算法的时间复杂度肯定大于**O(N2)** 了
 *  **滑动窗口算法思路:** 寻找一个可行解,然后优化这个可行解,最终找到最优解.左右指针轮流前进,窗口大小增增减减,不断向右滑动
    
     *  在字符串**S**中使用双指针中的左右指针技巧,初始化**left = right = 0,** 将索引闭区间\[left,right\]作为一个 **\[窗口\]**
     *  首先不断增加**right**指针来扩大窗口 **\[left, right\],** 直到窗口中的字符串符合包含**T**中的所有字符的要求
     *  然后,停止增加**right,** 通过不断增加**left**指针缩小窗口 **\[left,right\],** 直到窗口中的字符串不再符合包含T中的所有字符的要求.同时,每次增加**left,** 都要更新一轮结果
     *  重复以上两个步骤,直到**right**到达**S**的尽头
 *  **滑动窗口算法伪码框架:**

String s, t;
    int left = 0, right = 0;
    // res是符合要求的最小覆盖子串
    String res = s
    
    /* * 在s中寻找t的最小覆盖子串 */
     while (right < s.size()) { 
     	// window是对应的滑动窗口,即子串s[left,right]
     	window.add(s[right]);
     	right++;
     	while (window 符合要求) { 
     		// 如果这个窗口的子串更短,则更新res
     		res = minLen(res, window);
     		window.remove(s[left]);
     	}
     }
     return res;

*  **如何判断window中,也就是子串s\[left,right\]是否符合要求,是否包含t的所有字段:**
    
     *  可以使用两个哈希表当作计数器解决
        
         *  使用一个哈希表**needs**记录字符串**t**中包含的字符及出现次数
         *  使用另一个哈希表**window**记录当前 **\[窗口\]** 中包含的字符及出现的次数
     *  如果**window**包含所有**needs**中的键,并且这些键对应的值都大于等于**needs**中的值,那么当前窗口就符合要求,就可以开始移动**left**指针
 *  **滑动窗口算法框架优化:**

String s, t;
    int left = 0, right = 0
    String res = s;
    
    /* * 创建两个hash表作为字符的计数器 */
     unordered_map<char, int> window;
     unordered_map<char, int> needs;
     for (Char c : t) needs[c]++;
    
    // 记录window中符合要求的字符的个数
    int match = 0;
    
    /* * 在s中寻找t的最小覆盖子串 */
     while (right < s.size()) { 
     	char r = s[right]
     	if (needs.count(r)) { 
     		// 如果r在needs中,则将r加入window
     		window[r]++;
     		if (window[r] == needs[r]) { 
     			// 字符串r出现的次数符合要求
     			match++;
     		}
    	}
    	right++;
    	
    	// window中的字符串是符合要求的最小覆盖子串
    	while(match == needs.size()) { 
    		res = minLen(res, window);
    		char l = s[left];
    		if (needs.count(l)) { 
    			// 如果l在needs中,则将l移出window
    			window[l]--;
    			if (window[l] < needs[l]) { 
    				// 字符串l出现的次数不符合要求
    				match--;
    			}
    		}
    		left++
    	}
     }
     return res;

*  **完整代码:**

String minWindow(String s, String t) { 
    	// 记录最短子串的开始位置和长度
    	int start = 0, min_len = INIT_MAX;
    	int left = 0, right = 0;
    
    	// 创建两个Hash表作为字符的计数器
    	unordered_map<char, int> window;
    	unordered_map<char, int> needs;
    	for (char c : t) need[c]++;  
    
    	// 记录符合要求的字符个数
    	int match = 0;
    	
    	// 在s中寻找t的最小覆盖子串
    	while (right < s.size()) { 
    		char r = s[right];
    		if (needs.count(r)) { 
    			window[r]++;
    			if (window[r] == needs[r]) { 
    				match++;
    			}
    		}
    		right++;
    		
    		while (match == s.size()) { 
    			if (right - left < minLen) { 
    				// 如果滑动窗口的长度小于最小长度,则更新最小长度
    				start = left;
    				minLen = right - left;
    			}
    			char l = s[left];
    			if (needs.count(l)) { 
    				window[l]--;
    				if (window[l] < needs[l]) { 
    					match--
    				}
    			}
    			left++;	
    		}
    	}
    	return minLen == INIT_MAX ? "" : s.substr(start, minLen);	
    }

*  算法的时间复杂度为**O(M + N),M**和**N**分别是字符串**S**和**T**的长度
    
     *  因为首先用**for**循环遍历了字符串**T**来初始化**needs.** 时间为**O(N)**
     *  之后的两个循环最多执行**2M**次,时间复杂度为**O(M).** 因为**while**循环的次数就是双指针**left**和**right**走过的总路程

# 字母异位词 #

*  **题目:** 寻找字母相同,长度相同的子串
 *  **完整代码:**

vector<int> findAnagrams(String s, String t) { 
    	// 使用数组记录答案
    	vector<int> res;
    	int left = 0, right = 0;
    	 
    	// 创建两个Hash表作为字符的计数器
    	unordered_map<char, int> needs;
    	unordered_map<char, int> window;
    	 
    	// 记录要求匹配的字符的个数
    	int match = 0;
    
    	while (right < s.size()) { 
    		char r = s[right];
    		if (needs.count(r)) { 
    			window[r]++;
    			if (window[r] == needs[r]) { 
    				match++;
    			}
    		}
    		right++;
    
    		while (match == s.size()) { 
    			// 如果匹配的字符串和要求的长度相同则加入结果
    			if (right - left = t.size) { 
    				res.push_back(left)
    			}
    			char l = s[left];
    			if (needs.count(left)) { 
    				window[l]--;
    				if (window[l] < needs[l]) { 
    					match--;
    				}
    			}
    			left++
    		}
    	}
    	return res;
    }

# 无重复字符的最长子串 #

*  子串相关问题,首先想到使用滑动窗口技巧
 *  使用**window**作为计数器记录窗口中字符出现次数,然后向右移动**right,** 当**window**中出现重复字符时,开始移动**left**缩小窗口.重复执行:

int lengthOfLongestSubstring(String s) { 
    	int left = 0, right = 0;
    	
    	// 创建一个Hash表作为字符计数器
    	unordered_map<char, int> window;
    
    	// 记录字符串的长度
    	int res = 0;
    
    	while (right < s.size()) { 
    		char r = s[right];
    		window[r]++;
    		right++;
    		// 如果window中出现重复字符,则开始缩小window窗口
    		while (window[r] > 1) { 
    			char l = s[left];
    			window[l]--;
    			left++;
    		}
    		// 每次移动right时,更新res值
    		res = max(res, right - left);
    	}
    	return res;
    }

*  因为要求的是最长子串,所以需要在每次移动**right**增大窗口时更新**res**

# 滑动窗口技巧总结 #

*  **子串相关问题,首先想到使用滑动窗口技巧**
 *  **滑动窗口解题框架:**

int left = 0, right = 0;
    while (righ < s.size()) { 
    	window.add(s[right]);
    	right++;
    
    	while (valid) { 
    		window.remove(s[left]);
    		left++;
    	}
    }

> 最小覆盖子串完整代码:
> 
>     def minWindow(self, s : str, t : str) -> str:
>     	# 字符串开始位置和长度
>     	start, min_len = 0, float('Inf')
>     	left, right = 0, 0
>     	res = s
>      
>     	# 两个计数器
>     	needs = Counter(t)
>     	# defaultdict在访问的key不存在的时候会返回默认值0
>     	window = collections.defaultdict(int)
>     	 
>     	# 记录匹配要求的字符的个数
>     	match = 0
>     	
>     	while right < len(s):
>     		r = s[right]
>     		if needs[r] > 1:
>     			window[r] += 1
>     			if window[r] == needs[r]:
>     				match += 1
>     		right += 1
>     		
>     		while match = len(needs):
>     			if right - left < min_len:
>     				start = left
>     				min_len = right - left
>     			l = s[left]
>     			if needs[l] > 0:
>     				window[l] -= 1
>     				if window[l] < needs[l]:
>     					match -= 1
>     			left -= 1
>     	return s[start : start + min_len] if min_len != float("Inf") else ""