76. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例 2：
输入：s = "a", t = "a"
输出："a"
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-window-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路及方法
这道题挺难的也挺麻烦，跟我之前用的滑动窗口的解法思路一样，但是具体不类似，所以下一道题还是用的以前的方法，这道题具体解法参考这里，有框架。
class Solution {
public String minWindow(String s, String t) {
Map<Character, Integer> needs = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
// 存储t中每个字符的个数
for (char c : t.toCharArray()) {
needs.put(c, needs.getOrDefault(c, 0) + 1);
}
System.out.println(needs);
// 设置窗口左右界限
int left = 0, right = 0;
int valid = 0;
// 记录最小字串的起始点，长度
int start = 0, len = Integer.MAX_VALUE;
while (right < s.length()) {
char in = s.charAt(right);
// 右指针右移，窗口增大
right++;
if (needs.containsKey(in)) {
// 更新window
window.put(in, window.getOrDefault(in, 0) + 1);
// 判断窗口内部元素是否达到needs
if (window.get(in).equals(needs.get(in))) {
valid++;
}
}
// 判读是否要缩减窗口
while (valid == needs.size()) {
System.out.println(left);
System.out.println(right);
System.out.println();
// 覆盖最小长度
if (right - left < len) {
start = left;
len = right - left;
}
char out = s.charAt(left);
// 左指针右移，窗口减小
left++;
if (needs.containsKey(out)) {
if (window.get(out).equals(needs.get(out))) {
valid--;
}
window.put(out, window.getOrDefault(out, 0) - 1);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
}
结果如下：
438. 找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 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" 的异位词。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路及方法
这道题说说我的思路，用两个整型数组记录字符出现次数，一个是needs，记录需求p所有字符出现次数，另一个是window窗口，记录滑窗过程与p匹配。由于这道题窗口大小是不变的，所以我们设置windowSize = p的长度。
初始我们先统计p中字符的次数存入needs，以及将s的前windowSize位字符次数统计入window。开始从0遍历s到s.length() - windowSize，如果两个数组相等，说明满足条件，res存入此时的i，接着滑窗，移入第i + windowSize位，移出第i位。滑窗前需要判断i == s.length() - windowSize，因为此时需要判断最后一次，但不用再滑窗了。
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int[] needs = new int[26];
int[] window = new int[26];
List<Integer> res = new ArrayList<>();
if (p.length() > s.length()) return res;
// 设置窗口大小
int windowSize = p.length();
for (int i = 0; i < windowSize; i++) {
needs[p.charAt(i) - 'a']++;
window[s.charAt(i) - 'a']++;
}
// 滑窗
for (int i = 0; i <= s.length() - windowSize; i++) {
if (Arrays.equals(needs, window)) {
res.add(i);
}
// 停止滑窗
if (i == s.length() - windowSize) break;
window[s.charAt(i + windowSize) - 'a']++;
window[s.charAt(i) - 'a']--;
}
return res;
}
}
结果如下：
