滑动窗口总结
2020-06-01 本文已影响0人
南园故剑00
滑动窗口思路
- 在字符串s中使用双指针的最有指针技巧，初始化left=right=0，把索引左闭右开区间 [left,right) 称为一个窗口。
- 不断地增加right指针扩大窗口[left,right),直到窗口中的字符符合要求（包含了T中所有字符）
- 停止增加right，转而不断增加left指针缩小窗口[left,right),直到窗口中的字符串不再符合要求（不包含T中的所有字符了）。
同时每次增加left，我们都要更新一轮结果 - 重复2-3，直到right到达字符串s的尽头。
在第二步中寻找一个可行解、在第三步在优化这个可行解，最终找到最优解。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。
模板
int left = 0, right = 0;
while(right<s.size(){
window.add(s.charAt(right));
right++;
whild(valid){
window.remove(s.charAt(left));
left++;
}
}
套模板四个问题
//给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
//
// 示例：
//
// 输入: S = "ADOBECODEBANC", T = "ABC"
//输出: "BANC"
//
// 说明：
//
//
// 如果 S 中不存这样的子串，则返回空字符串 ""。
// 如果 S 中存在这样的子串，我们保证它是唯一的答案。
//
// Related Topics 哈希表 双指针 字符串 Sliding Window
package leetcode.editor.cn;
import java.util.HashMap;
import java.util.Map;
//Java：最小覆盖子串
public class P76MinimumWindowSubstring {
public static void main(String[] args) {
Solution solution = new P76MinimumWindowSubstring().new Solution();
// TO TEST
// System.out.println("432101234".substring(0, 1));
String S = "ADOBECODEBANC", T = "ABC";
System.out.println(solution.minWindow(S, T));
}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public String minWindow0(String s, String t) {
int left = 0, right = 0;
int start = 0, minLen = Integer.MAX_VALUE;
Map<Character, Integer> window = new HashMap<>();
Map<Character, Integer> needs = new HashMap<>();
for (char c : t.toCharArray()) {
needs.put(c, needs.getOrDefault(c, 0) + 1);
}
//记录window中已经有多少字符符合要求了
int macth = 0;
while (right < s.length()) {
//c1是移入窗口的字符
char c1 = s.charAt(right);
right++;
if (needs.getOrDefault(c1, 0) != 0) {
window.put(c1, window.getOrDefault(c1, 0) + 1);
if (window.get(c1).equals(needs.get(c1))) {
//字符c1的出现次数符合要求了
macth++;
}
}
//window中的字符串已经符合needs的要求了
while (macth == needs.size()) {
if (right - left < minLen) {
//更新最小字串的长度和位置
start = left;
minLen = right - left;
}
char c2 = s.charAt(left);
if (needs.get(c2) != null && needs.get(c2) != 0) {
//将c2字符移出window
window.put(c2, window.getOrDefault(c2, 0) - 1);
if (window.get(c2) < needs.get(c2)) {
//c2字符出现次数不再符合要求
macth--;
}
}
left++;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, minLen);
}
public String minWindow(String s, String t) {
//用来统计t中每个字符出现次数
int[] needs = new int[128];
//用来统计滑动窗口中每个字符出现次数
int[] window = new int[128];
for (int i = 0; i < t.length(); i++) {
needs[t.charAt(i)]++;
}
int left = 0;
int right = 0;
String res = "";
//目前有多少个字符
int count = 0;
//用来记录最短需要多少个字符。
int minLength = s.length() + 1;
while (right < s.length()) {
char ch = s.charAt(right);
window[ch]++;
if (needs[ch] > 0 && needs[ch] >= window[ch]) {
count++;
}
//移动到不满足条件为止
while (count == t.length()) {
ch = s.charAt(left);
if (needs[ch] > 0 && needs[ch] >= window[ch]) {
count--;
}
if (right - left + 1 < minLength) {
minLength = right - left + 1;
res = s.substring(left, right + 1);
}
window[ch]--;
left++;
}
right++;
}
return res;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
//给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
//
// 字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
//
// 说明：
//
//
// 字母异位词指字母相同，但排列不同的字符串。
// 不考虑答案输出的顺序。
//
//
// 示例 1:
//
//
//输入:
//s: "cbaebabacd" p: "abc"
//
//输出:
//[0, 6]
//
//解释:
//起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
//起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
//
//
// 示例 2:
//
//
//输入:
//s: "abab" p: "ab"
//
//输出:
//[0, 1, 2]
//
//解释:
//起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
//起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
//起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
//
// Related Topics 哈希表
package leetcode.editor.cn;
import java.util.ArrayList;
import java.util.List;
//Java：找到字符串中所有字母异位词
public class P438FindAllAnagramsInAString {
public static void main(String[] args) {
Solution solution = new P438FindAllAnagramsInAString().new Solution();
// TO TEST
}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public List<Integer> findAnagrams(String s, String p) {
char[] arrS = s.toCharArray();
char[] arrP = p.toCharArray();
//接收最后返回的结果
List<Integer> ans = new ArrayList<>();
//定义一个needs数据来看arrP中包含元素的个数
int[] needs = new int[26];
//定义一个window数组来看滑动窗口中是否有arrP中的元素，并记录出现的个数
int[] window = new int[26];
//现将arrP中的元素保存到needs数组中
for (char c : arrP) {
needs[c - 'a'] += 1;
}
//定义滑动窗口的两端
int left = 0;
int right = 0;
//右窗口不断向右一定
while (right < arrS.length) {
// curR 为当前元素的在数组中的索引
int curR = arrS[right] - 'a';
right++;
//将窗口当前访问到的元素cur个数+1
window[curR] += 1;
//当window数组中cur比needs数组中对应元素的个数要多的时候就该移动左窗口指针
while (window[curR] > needs[curR]) {
int curL = arrS[left] - 'a';
left++;
//将左窗口当前访问到的元素curL个数减1
window[curL] -= 1;
}
//这里将所有符合要求的左窗口索引放入到了接收结果的List中
if (right - left == arrP.length) {
ans.add(left);
}
}
return ans;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
//给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
//
// 示例 1:
//
// 输入: "abcabcbb"
//输出: 3
//解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
//
//
// 示例 2:
//
// 输入: "bbbbb"
//输出: 1
//解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
//
//
// 示例 3:
//
// 输入: "pwwkew"
//输出: 3
//解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
// 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
//
// Related Topics 哈希表 双指针 字符串 Sliding Window
package leetcode.editor.cn;
//Java：无重复字符的最长子串
public class P3LongestSubstringWithoutRepeatingCharacters{
public static void main(String[] args) {
Solution solution = new P3LongestSubstringWithoutRepeatingCharacters().new Solution();
// TO TEST
}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int lengthOfLongestSubstring(String s) {
int left = 0, right = 0;
int[] window = new int[26];
int res = 0;
while (right < s.length()) {
int c = s.charAt(right) - 'a';
window[c]++;
right++;
//如果window中出现重复字符
while (window[c] > 1) {
int c2 = s.charAt(left) - 'a';
window[c2]--;
left++;
}
res = Math.max(res, right - left);
}
return res;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
//给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
//
// 换句话说，第一个字符串的排列之一是第二个字符串的子串。
//
// 示例1:
//
//
//输入: s1 = "ab" s2 = "eidbaooo"
//输出: True
//解释: s2 包含 s1 的排列之一 ("ba").
//
//
//
//
// 示例2:
//
//
//输入: s1= "ab" s2 = "eidboaoo"
//输出: False
//
//
//
//
// 注意：
//
//
// 输入的字符串只包含小写字母
// 两个字符串的长度都在 [1, 10,000] 之间
//
// Related Topics 双指针 Sliding Window
package leetcode.editor.cn;
import java.util.Collections;
//Java：字符串的排列
public class P567PermutationInString {
public static void main(String[] args) {
Solution solution = new P567PermutationInString().new Solution();
// TO TEST
}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public boolean checkInclusion(String s1, String s2) {
//排除异常的边界情况，也限定了模式串的长度
if (s1.length() > s2.length()) {
return false;
}
//匹配采用的窗口大小为模式串大小
int windowSize = s1.length();
//模式串的字典：可以看作是一种频率分布
int[] map1 = new int[26];
//动态更新的匹配窗口字典
int[] map2 = new int[26];
for (int i = 0; i < windowSize; i++) {
map1[s1.charAt(i) - 'a']++;
map2[s2.charAt(i) - 'a']++;
}
//对于每一轮滑窗查询，如果两个字典相等（评论分布一直，则命中）
for (int i = windowSize; i < s2.length(); i++) {
//两个字典相等，则命中
if (Collections.singletonList(map1).equals(Collections.singletonList(map2))) {
return true;
}
//否则，向右滑窗：滑窗对于hash表的操作变为对应频率的增减
map2[s2.charAt(i - windowSize) - 'a']--;
map2[s2.charAt(i) - 'a']++;
}
//整个算法采用左闭右开区间，最后还有一个窗口没有判断
return Collections.singletonList(map1).equals(Collections.singletonList(map2));
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
待实现的问题
1、3. 无重复字符的最长子串
2、30. 串联所有单词的子串
3、76. 最小覆盖子串
4、159. 至多包含两个不同字符的最长子串
5、209. 长度最小的子数组
6、239. 滑动窗口最大值
7、340. 至多包含 K 个不同字符的最长子串
8、438. 找到字符串中所有字母异位词
9、567. 字符串的排列
10、632. 最小区间
11、727. 最小窗口子序列
