力扣Hot100系列3（Java）——[滑动窗口]总结（无重复字符的最长子串，找到字符串中所有字母异位词）

前言

本文记录力扣Hot100里面关于滑动窗口的两道题，包括常见解法和一些关键步骤理解，也有例子便于大家理解

`

一、无重复字符的最长子串

1.题目

题目
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。注意 “bca” 和 “cab” 也是正确答案。

示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

2.代码

classSolution{publicintlengthOfLongestSubstring(Strings){// 哈希集合：用于记录当前窗口中已经出现过的字符（判断是否重复）Set<Character>occ=newHashSet<Character>();intn=s.length();// 字符串长度// 右指针 rk：初始值为 -1，代表窗口的右边界还未开始（在字符串最左侧外面）intrk=-1,ans=0;// ans 记录最长子串的长度// 左指针 i 从 0 开始，逐步向右移动（枚举窗口的左边界）for(inti=0;i<n;++i){if(i!=0){// 左指针向右移动一格时，移除窗口中 i-1 位置的字符（因为窗口左边界右移，该字符不再在窗口内）occ.remove(s.charAt(i-1));}// 右指针不断向右移动，扩展窗口：// 条件1：rk+1 < n（右指针不越界）确保下一个字符不越界（在字符串范围内）。// 条件2：窗口中不包含下一个字符（s.charAt(rk+1)）确保下一个字符不在当前窗口中（无重复）while(rk+1<n&&!occ.contains(s.charAt(rk+1))){// 将下一个字符加入集合（标记为已出现）occ.add(s.charAt(rk+1));// 右指针右移一格++rk;}// 此时窗口 [i...rk] 是当前左边界 i 下的最长无重复子串// 更新最长长度（当前窗口长度 = rk - i + 1）ans=Math.max(ans,rk-i+1);}returnans;}}

3.关键步骤

// 左指针 i 从 0 开始，逐步向右移动（枚举窗口的左边界）for(inti=0;i<n;++i){if(i!=0){// 左指针向右移动一格时，移除窗口中 i-1 位置的字符（因为窗口左边界右移，该字符不再在窗口内）occ.remove(s.charAt(i-1));}// 右指针不断向右移动，扩展窗口：// 条件1：rk+1 < n（右指针不越界）确保下一个字符不越界（在字符串范围内）。// 条件2：窗口中不包含下一个字符（s.charAt(rk+1)）确保下一个字符不在当前窗口中（无重复）while(rk+1<n&&!occ.contains(s.charAt(rk+1))){// 将下一个字符加入集合（标记为已出现）occ.add(s.charAt(rk+1));// 右指针右移一格++rk;}// 此时窗口 [i...rk] 是当前左边界 i 下的最长无重复子串// 更新最长长度（当前窗口长度 = rk - i + 1）ans=Math.max(ans,rk-i+1);}

循环内的逻辑是：右指针从左到右逐个向后移动（全程单向不回退），左指针初始位置固定；当右指针遇到的新字符导致窗口内出现重复时，左指针会向右移动以收缩窗口（直到窗口内无重复字符）；每次右指针移动后，都会计算当前窗口的长度并更新最大长度；整个过程重复至右指针遍历完字符串所有字符（左指针仅在窗口不满足条件时收缩，并非主动 “出界”）。
而窗口实际上就是左指针和右指针之间的闭区间 [i ，rk] （即对应原字符的子串）。

关于为什么是++rk;
逻辑上的顺序不同：++rk 是 “主动将指针移到新位置”，而 rk++ 是 “先保留旧位置，再被动移到新位置”。这种顺序差异在复杂场景（如嵌套判断）中可能导致逻辑混乱，而 ++rk 更直观地体现了 “扩展窗口右边界” 的意图，避免歧义。

4.例子

演示：以 s = “abcabcbb” 为例

1. 初始状态：i=0，rk=-1，occ 为空，ans=0。

• 左指针 i=0（未移动过，无需移除字符）。
• 右指针扩展：rk+1=0（字符 ‘a’ 不在 occ 中）→ 加入 occ，rk=0；继续：rk+1=1（‘b’ 不在 occ 中）→ 加入，rk=1；继续：rk+1=2（‘c’ 不在 occ 中）→ 加入，rk=2；继续：rk+1=3（‘a’ 已在 occ 中）→ 停止扩展。
• 当前窗口 [0,2]（“abc”），长度 3 → ans=3。

2. 左指针 i=1**：

• 移除 i-1=0 位置的字符 ‘a’ → occ 现在包含 {‘b’,‘c’}。
• 右指针扩展：rk+1=3（‘a’ 不在 occ 中）→ 加入，rk=3；继续：rk+1=4（‘b’ 已在 occ 中）→ 停止扩展。
• 当前窗口 [1,3]（“bca”），长度 3 → ans 保持 3。

3. 左指针 i=2**：

• 移除 i-1=1 位置的字符 ‘b’ → occ 现在包含 {‘c’,‘a’}。
• 右指针扩展：rk+1=4（‘b’ 不在 occ 中）→ 加入，rk=4；继续：rk+1=5（‘c’ 已在 occ 中）→ 停止扩展。
• 当前窗口 [2,4]（“cab”），长度 3 → ans 保持 3。

4. 左指针 i=3**：

• 移除 i-1=2 位置的字符 ‘c’ → occ 现在包含 {‘a’,‘b’}。
• 右指针扩展：rk+1=5（‘c’ 不在 occ 中）→ 加入，rk=5；继续：rk+1=6（‘b’ 已在 occ 中）→ 停止扩展。
• 当前窗口 [3,5]（“abc”），长度 3 → ans 保持 3。

5. 后续步骤（i=4 到 i=7）：右指针扩展时会更快遇到重复字符，窗口长度逐渐减小（如 2、1 等），ans 始终保持 3。
   最终返回 3，符合预期结果。

二、找到字符串中所有字母异位词

1.题目

题目
给定两个字符串 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” 的异位词。

2.代码

classSolution{publicList<Integer>findAnagrams(Strings,Stringp){intsLen=s.length(),pLen=p.length();// 边界条件：如果s的长度小于p，不可能有异位词，直接返回空列表if(sLen<pLen){returnnewArrayList<Integer>();}List<Integer>ans=newArrayList<Integer>();// 用两个数组记录字符频率（26个小写字母，索引0对应'a'，1对应'b'...）int[]sCount=newint[26];int[]pCount=newint[26];// 初始化：统计p的字符频率，以及s中第一个窗口（0到pLen-1）的字符频率for(inti=0;i<pLen;++i){// s中第i个字符的频率+1（s.charAt(i) - 'a' 得到0-25的索引）++sCount[s.charAt(i)-'a'];// p中第i个字符的频率+1++pCount[p.charAt(i)-'a'];}// 检查初始窗口是否与p是异位词（频率数组相同）if(Arrays.equals(sCount,pCount)){ans.add(0);// 起始索引0符合条件}// 滑动窗口：从左到右移动窗口，更新频率数组并检查// 窗口移动次数 = sLen - pLen（保证窗口不越界）for(inti=0;i<sLen-pLen;++i){// 移除窗口左侧的字符（左边界右移，该字符不再在窗口内）--sCount[s.charAt(i)-'a'];// 加入窗口右侧的新字符（右边界右移，纳入新字符）++sCount[s.charAt(i+pLen)-'a'];// 检查当前窗口（起始索引i+1）是否与p是异位词if(Arrays.equals(sCount,pCount)){ans.add(i+1);// 记录起始索引}}returnans;}}

3.关键理解

本题与第一题不同的地方在于，本题的滑动窗口长度是固定的，就是字符串p的长度

核心：
用索引代表字母，用索引上具体的值代表频率

for(inti=0;i<pLen;++i){// s中第i个字符的频率+1（s.charAt(i) - 'a' 得到0-25的索引）++sCount[s.charAt(i)-'a'];// p中第i个字符的频率+1++pCount[p.charAt(i)-'a'];}

统计目标串 p 中每个字符的出现频率（存入 pCount 数组）；
统计原串 s 中第一个窗口（起始索引 0、长度等于 pLen）的字符频率（存入 sCount 数组）。

for(inti=0;i<sLen-pLen;++i){// 移除窗口左侧的字符（左边界右移，该字符不再在窗口内）--sCount[s.charAt(i)-'a'];// 加入窗口右侧的新字符（右边界右移，纳入新字符）++sCount[s.charAt(i+pLen)-'a'];// 检查当前窗口（起始索引i+1）是否与p是异位词if(Arrays.equals(sCount,pCount)){ans.add(i+1);// 记录起始索引}}

为什么是 i < sLen- pLen:
窗口右边界的计算：因为循环内含有++sCount[s.charAt(i + pLen) - ‘a’];
i + pLen（加入的新字符索引），这个索引必须 < sLen（否则超出 s 的范围）。

我们看具体的例子理解一下。

4.例子

s = "cbaebabacd"（长度10）、p = "abc"（长度3）为例，完整走一遍代码执行流程

第一步：初始化基础变量

sLen = 10，pLen = 3（sLen > pLen）；

• ans = []（空列表，用于存结果）；
• sCount = [0,0,0,...,0]（26个0），pCount = [0,0,0,...,0]（26个0）。

第二步：统计初始频率（循环i=0~2）

循环结束后：

• sCount = [1,1,1,0,0,...0]（仅a/b/c各1次，其余0）；
• pCount = [1,1,1,0,0,...0]（仅a/b/c各1次，其余0）。

第三步：判断初始窗口（i=0）

Arrays.equals(sCount, pCount)→ 所有索引值相等 → 返回true →ans.add(0)→ans = [0]。

第四步：滑动窗口循环（i=0~6，共7次循环，i < 10-3=7）

循环i=0（处理窗口起始索引1）

• 移除左边界：s[0] = c → 索引2 →sCount[2] -=1→ sCount[2] = 0；
• 加入右边界：s[0+3] = s[3] = e → 索引4 →sCount[4] +=1→ sCount[4] = 1；
• 此时sCount = [1,1,0,0,1,...0]，pCount = [1,1,1,0,0,...0]；
• Arrays.equals对比：索引2（0≠1）→ false → 不加入ans。

循环i=1（处理窗口起始索引2）

移除左边界：s[1] = b → 索引1 →sCount[1] -=1→ sCount[1] = 0；

• 加入右边界：s[1+3] = s[4] = b → 索引1 →sCount[1] +=1→ sCount[1] = 1；
• 此时sCount = [1,1,0,0,1,...0]，pCount = [1,1,1,0,0,...0]；
• Arrays.equals对比：索引2（0≠1）→ false → 不加入ans。

循环i=2（处理窗口起始索引3）

移除左边界：s[2] = a → 索引0 →sCount[0] -=1→ sCount[0] = 0；

• 加入右边界：s[2+3] = s[5] = a → 索引0 →sCount[0] +=1→ sCount[0] = 1；
• 此时sCount = [1,1,0,0,1,...0]，pCount = [1,1,1,0,0,...0]；
• Arrays.equals对比：索引2（0≠1）→ false → 不加入ans。

循环i=3（处理窗口起始索引4）

移除左边界：s[3] = e → 索引4 →sCount[4] -=1→ sCount[4] = 0；

• 加入右边界：s[3+3] = s[6] = b → 索引1 →sCount[1] +=1→ sCount[1] = 2；
• 此时sCount = [1,2,0,0,0,...0]，pCount = [1,1,1,0,0,...0]；
• Arrays.equals对比：索引1（2≠1）、索引2（0≠1）→ false → 不加入ans。

循环i=4（处理窗口起始索引5）

移除左边界：s[4] = b → 索引1 →sCount[1] -=1→ sCount[1] = 1；

• 加入右边界：s[4+3] = s[7] = a → 索引0 →sCount[0] +=1→ sCount[0] = 2；
• 此时sCount = [2,1,0,0,0,...0]，pCount = [1,1,1,0,0,...0]；
• Arrays.equals对比：索引0（2≠1）、索引2（0≠1）→ false → 不加入ans。

循环i=5（处理窗口起始索引6）

移除左边界：s[5] = a → 索引0 →sCount[0] -=1→ sCount[0] = 1；

• 加入右边界：s[5+3] = s[8] = c → 索引2 →sCount[2] +=1→ sCount[2] = 1；
• 此时sCount = [1,1,1,0,0,...0]，pCount = [1,1,1,0,0,...0]；
• Arrays.equals对比**：所有索引值相等 → true →ans.add(6)→ans = [0,6]。

循环i=6（处理窗口起始索引7）

移除左边界：s[6] = b → 索引1 →sCount[1] -=1→ sCount[1] = 0；

• 加入右边界：s[6+3] = s[9] = d → 索引3 →sCount[3] +=1→ sCount[3] = 1；
• 此时sCount = [1,0,1,1,0,...0]，pCount = [1,1,1,0,0,...0]；
• Arrays.equals对比：索引1（0≠1）、索引3（1≠0）→ false → 不加入ans。

第五步：返回结果

最终ans = [0,6]，即s中起始索引0（子串"cba"）和6（子串"bac"）是p的异位词。

核心总结

1. 本题中滑动窗口的核心是「移除左边界+加入右边界」，保证窗口长度固定为3O（字符串p的长度）；
2. Arrays.equals逐索引对比频率数组，只有全相等才判定为异位词；