【算法系列篇】滑动窗口-1https://developer.aliyun.com/article/1430490
6.找到字符串中所有字母异位词
https://leetcode.cn/problems/find-all-anagrams-in-a-string/
6.1 题目要求
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。 示例 1:
示例 2:
输入: s = "abab", p = "ab" 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
提示:
1 <= s.length, p.length <= 3 * 104 s 和 p 仅包含小写字母
class Solution { public List<Integer> findAnagrams(String s, String p) { } }
6.2 做题思路
这道题其实就相当于使用一个大小为 p 字符串长度的框从 s 字符串头部开始框 p 字符串长度的字符串，然后判断框起来的字符串是否是 p 字符串的异位词。
窗口中的大小是确定的，最终的窗口的大小是p字符串的长度，也就是说我们的判断条件就是窗口内的字符串是否是p字符串的异位词，这也是解决这道题的关键。那么我们应该如何解决呢？同样是使用两个哈希表，第一个哈希表统计p字符串每个单词出现的次数，当进窗口的时候，第二个哈希表中该字符出现的次数就加一，并且如果将这个字符添加进哈希表之后，该哈希表中对应字符出现的次数小于等于第一个哈希表对应字符出现的次数，就说明进窗口的这个字符为有效字符，我们使用 count 来记录有效字符的个数，count++，当 count 等于 p 字符串的长度时，就需要更新结果：将 left 的坐标添加进列表中。
6.3 Java代码实现
class Solution { public List<Integer> findAnagrams(String ss, String pp) { List<Integer> list = new ArrayList<>(); char[] s = ss.toCharArray(); char[] p = pp.toCharArray(); int[] hash1 = new int[26]; int[] hash2 = new int[26]; for(char ch : p) hash1[ch - 'a']++; int len = p.length; for(int left = 0, right = 0,count = 0; right < s.length; right++) { char in = s[right]; if(++hash2[in - 'a'] <= hash1[in - 'a']) count++; if(right - left + 1 > len) { char out = s[left++]; if(hash2[out - 'a']-- <= hash1[out - 'a']) count--; } if(count == len) { list.add(left); } } return list; } }
7.串联所有单词的子串
https://leetcode.cn/problems/substring-with-concatenation-of-all-words/
7.1 题目要求
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如，如果 words = [“ab”,“cd”,“ef”]， 那么 “abcdef”， “abefcd”，“cdabef”， “cdefab”，“efabcd”， 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
示例 1：
输入：s = "barfoothefoobarman", words = ["foo","bar"] 输出：[0,9] 解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。 子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。 子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。 输出顺序无关紧要。返回 [9,0] 也是可以的。
示例 2：
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] 输出：[] 解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。 s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。 所以我们返回一个空数组。
示例 3：
输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] 输出：[6,9,12] 解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。 子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。 子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。 子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。
提示：
1 <= s.length <= 104 1 <= words.length <= 5000 1 <= words[i].length <= 30 words[i] 和 s 由小写英文字母组成
class Solution { public List<Integer> findSubstring(String s, String[] words) { } }
7.2 做题思路
这道题目跟上面的一个题目是类似的，只是这里将字母换成了单词，所以我们可以仿照上面一个题的思路，将words数组中的每个字符串当作一个字母，s 字符串每与words数组中每个单词相同长度的字符串作为一个字母。
因为不仅可以从 b 开始，将字符数组分为多个字符串，还可以从a和r开始，所以这里我们需要进行 words 数组中每个单词长度的循环次数的操作。
这里的哈希表用数组就不容易模拟了，所以这里就需要用到 HashMap
7.3 Java代码实现
class Solution { public List<Integer> findSubstring(String s, String[] words) { List<Integer> list = new ArrayList<>(); Map<String,Integer> map1 = new HashMap<>(); for(String tmp : words) { map1.put(tmp,map1.getOrDefault(tmp,0) + 1); } int len = words.length; //求words数组的大小 int m = words[0].length(); //求words数组中每个单词的长度 for(int i = 0; i < m; i++) { Map<String,Integer> map2 = new HashMap<>(); for(int left = i, right = i, count = 0; right <= s.length()-m; right += m) { String in = s.substring(right,right + m); map2.put(in,map2.getOrDefault(in,0) + 1); if(map2.get(in) <= map1.getOrDefault(in,0)) count++; if(right - left + 1 > len * m) { String out = s.substring(left,left + m); if(map2.get(out) <= map1.getOrDefault(out,0)) count--; map2.put(out,map2.get(out) - 1); left += m; } if(count == len) list.add(left); } } return list; } }
8.最小覆盖字串
https://leetcode.cn/problems/minimum-window-substring/
8.1 题目要求
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2：
输入：s = "a", t = "a" 输出："a" 解释：整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。
提示
m == s.length n == t.length 1 <= m, n <= 105 s 和 t 由英文字母组成
class Solution { public String minWindow(String s, String t) { } }
8.2 做题思路
因为这道题目中说了，可以出现重复的字符，所以这道题的判断条件就是窗口中是否含有 t 字符串中的所有字符，并且窗口中的每个字符出现的次数必须大于 t 字符串中每个字符出现的次数。那么这道题的步骤主要分为两步：
- 在s字符串中，找到含有 t 字符串中含有的所有字符的窗口
- 在这个窗口中找长度最小的子串
8.3 Java代码实现
class Solution { public String minWindow(String ss, String tt) { char[] s = ss.toCharArray(); char[] t = tt.toCharArray(); int[] hash1 = new int[128]; int[] hash2 = new int[128]; int kinds = 0; for(char ch : t) { if(hash1[ch]++ == 0) kinds++; } int begin = -1; int minLen = Integer.MAX_VALUE; for(int left = 0, right = 0,count = 0; right < s.length; right++) { char in = s[right]; if(++hash2[in] == hash1[in]) count++; while(count == kinds) { if(right - left + 1 < minLen) { begin = left; minLen = right - left + 1; } char out = s[left++]; if(hash2[out]-- == hash1[out]) count--; } } if(begin == -1) return new String(); else return ss.substring(begin,begin + minLen); } }
总结
当涉及到解决子串或子数组的问题时，滑动窗口算法是一种非常有效的技术。它通过维护一个窗口，该窗口在字符串或数组上滑动，以解决特定问题。
滑动窗口算法的主要思想是使用两个指针，一个指向窗口的起始位置，另一个指向窗口的结束位置。通过调整这两个指针，可以扩展或收缩窗口，以找到所需的解。算法的关键是确定窗口的移动规则以及如何在移动过程中更新解。
下面是滑动窗口算法的一般步骤：
初始化窗口的起始指针和结束指针，使其指向合理的位置。
进入一个循环，不断尝试扩展窗口，直到窗口无法再扩展为止。
在每次窗口移动时，更新解（如果有必要）。
如果窗口仍然满足问题的要求，尝试收缩窗口，以寻找更优的解。
重复步骤3和4，直到窗口完全收缩并处理完所有元素。
滑动窗口算法的优点是其时间复杂度通常是线性的，因为它避免了对每个子串或子数组的重复计算，节约了计算资源。它也通常可以在O(1)的空间复杂度下完成。
滑动窗口算法常用于解决一些经典问题，例如字符串匹配、子数组和子串求和、最长/最短子数组等。通过适当定义窗口的移动规则和解的更新方式，可以针对不同的具体问题进行定制化的实现。
总结而言，滑动窗口算法是一种高效的解决子串或子数组问题的方法。它的核心思想是通过维护一个窗口，在问题的限定条件下移动窗口的起始和结束指针，同时利用解的特性来优化计算过程。使用滑动窗口算法可以提高问题的解决效率，并减少不必要的计算。
