一、滑动窗口模板
// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。
import java.util.HashMap;
import java.util.Map;
public class Main {
/* 滑动窗口算法框架 */
public static void slidingWindow(String s) {
// 用合适的数据结构记录窗口中的数据，根据具体场景变通
// 比如说，我想记录窗口中元素出现的次数，就用 map
// 我想记录窗口中的元素和，就用 int
Map<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
while (right < s.length()) {
// c 是将移入窗口的字符
char c = s.charAt(right);
window.put(c, window.getOrDefault(c, 0) + 1);
// 增大窗口
right++;
// 进行窗口内数据的一系列更新
// ...
/*** debug 输出的位置 ***/
// 注意在最终的解法代码中不要 print
// 因为 IO 操作很耗时，可能导致超时
System.out.printf("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗口是否要收缩
while (left < right && window needs shrink) {
// d 是将移出窗口的字符
char d = s.charAt(left);
window.put(d, window.get(d) - 1);
// 缩小窗口
left++;
// 进行窗口内数据的一系列更新
// ...
}
}
}
public static void main(String[] args) {
slidingWindow("your string here");
}
}
背完模板后，还需要考虑什么？
1、什么时候应该移动 right 扩大窗口？窗口加入字符时，应该更新哪些数据？
2、什么时候窗口应该暂停扩大(满足了条件)，开始移动 left 缩小窗口？从窗口移出字符时，应该更新哪些数据？
3、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
如果一个字符进入窗口，应该增加 window 计数器；如果一个字符将移出窗口的时候，应该减少 window 计数器；当 valid 满足 need 时应该收缩窗口；应该在收缩窗口的时候更新最终结果。
1.最小覆盖子串
- s是长字符串，t是短字符串
- need.size() 是 t中 不同字符的种类数，同样的valid 每加1表示的是一个字符被满足，而不是某个字符的数量匹配上了一次
/**
* 求字符串 s 中包含字符串 t 所有字符的最小子串
* @param s 源字符串
* @param t 给定字符串
* @return 满足条件的最小子串
*/
public String minWindow(String s, String t) {
// 用于记录需要的字符和窗口中的字符及其出现的次数
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
// 统计 t 中各字符出现次数
for (char c : t.toCharArray())
need.put(c, need.getOrDefault(c, 0) + 1);
int left = 0, right = 0;
int valid = 0; // 窗口中满足需要的字符个数
// 记录最小覆盖子串的起始索引及长度
int start = 0, len = Integer.MAX_VALUE;
while (right < s.length()) {
// c 是将移入窗口的字符
char c = s.charAt(right);
// 扩大窗口
right++;
// 进行窗口内数据的一系列更新
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c)))
valid++; // 只有当 window[c] 和 need[c] 对应的出现次数一致时，才能满足条件，valid 才能 +1
}
// 判断左侧窗口是否要收缩
while (valid == need.size()) {
// 更新最小覆盖子串
if (right - left < len) {
start = left;
len = right - left;
}
// d 是将移出窗口的字符
char d = s.charAt(left);
// 缩小窗口
left++;
// 进行窗口内数据的一系列更新
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d)))
valid--; // 只有当 window[d] 内的出现次数和 need[d] 相等时，才能 -1
window.put(d, window.get(d) - 1);
}
}
}
// 返回最小覆盖子串
return len == Integer.MAX_VALUE ?
"" : s.substring(start, start + len);
}
在Java中，对于对象类型（如Integer、String等），我们通常使用equals()方法来判断它们的值是否相等，而不是使用等号==。
原因是，等号 == 在比较对象类型时，比较的是对象的引用（内存地址），而不是对象的实际值。也就是说，使用 == 来比较两个对象，只有当它们引用同一个对象时，才会返回true。
然而，equals()方法被设计用来比较对象的值是否相等。对于String类型，equals()方法已经被重写，用于比较两个字符串的内容是否相等。对于Integer类型，equals()方法也被重写，用于比较两个整数值是否相等。
因此，如果我们想要比较两个对象的值是否相等，应该使用equals()方法。例如，使用s1.equals(s2)来比较两个字符串s1和s2的内容是否相等。
需要注意的是，有些对象类型（如Integer、Character等）具有自动拆装箱的功能，可以直接使用等号==进行比较。这是因为Java会自动将基本类型转换为对应的包装类型，以便进行比较。但是，对于其他对象类型，我们仍然应该使用equals()方法来确保正确的比较
2.字符串的排列
class Solution {
public boolean checkInclusion(String s1, String s2) {
HashMap<Character, Integer> need = new HashMap<>();
HashMap<Character, Integer> window = new HashMap<>();
for(int i = 0; i < s1.length(); i++){
char c = s1.charAt(i);
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0,right = 0;
int valid = 0;
while(right < s2.length()){
char c = s2.charAt(right);
right++;
if(need.containsKey(c)){
window.put(c, window.getOrDefault(c, 0) + 1);
if(window.get(c).equals(need.get(c)))
valid++;
}
//判断左窗口是否要收缩
while(right - left >= s1.length()){
//在这里判断是否找到了合法的子串
if(valid == need.size())
return true;
char d = s2.charAt(left);
left++;
if(need.containsKey(d)){
if(window.get(d).equals(need.get(d)))
valid--;
window.put(d, window.getOrDefault(d, 0) - 1);
}
}
}
//未找到符合条件的子串
return false;
}
}
3.找出所有的字母异位词438
// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。
public List<Integer> findAnagrams(String s, String t) {
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
char c = t.charAt(i);
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
List<Integer> res = new ArrayList<>(); // 记录结果
while (right < s.length()) {
char c = s.charAt(right);
right++;
// 进行窗口内数据的一系列更新
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
// 判断左侧窗口是否要收缩
while (right - left >= t.length()) {
// 当窗口符合条件时，把起始索引加入 res
if (valid == need.size()) {
res.add(left);
}
char d = s.charAt(left);
left++;
// 进行窗口内数据的一系列更新
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.get(d) - 1);
}
}
}
return res;
}
4.最长无重复子串
int lengthOfLongestSubstring(String s) {
Map<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
int res = 0; // 记录结果
while (right < s.length()) {
char c = s.charAt(right);
right++;
// 进行窗口内数据的一系列更新
window.put(c, window.getOrDefault(c, 0) + 1);
// 判断左侧窗口是否要收缩
while (window.get(c) > 1) {
char d = s.charAt(left);
left++;
// 进行窗口内数据的一系列更新
window.put(d, window.get(d) - 1);
}
// 在这里更新答案
res = Math.max(res, right - left);
}
return res;
}