当前位置：首页 > news >正文

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

news 2026/8/21 5:13:56

文章目录

前言
一、无重复字符的最长子串
- 1.题目
- 2.代码
- 3.关键步骤
- 4.例子
二、找到字符串中所有字母异位词
- 1.题目
- 2.代码
- 3.关键理解
- 4.例子
- - 第一步：初始化基础变量
  - 第二步：统计初始频率（循环 `i=0~2`）
  - 第三步：判断初始窗口（i=0）
  - 第四步：滑动窗口循环（`i=0~6`，共7次循环，`i < 10-3=7`）
  - 第五步：返回结果
  - 核心总结

前言

本文记录力扣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” 为例

初始状态：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。

左指针 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。

左指针 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。

左指针 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。

后续步骤（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`）

循环i	操作sCount（s的初始窗口：s[0],s[1],s[2] = c,b,a）	操作pCount（p[0],p[1],p[2] = a,b,c）
0	s[0] = c → 索引2 →`sCount[2] +=1`→ sCount[2]=1	p[0] = a → 索引0 →`pCount[0] +=1`→ pCount[0]=1
1	s[1] = b → 索引1 →`sCount[1] +=1`→ sCount[1]=1	p[1] = b → 索引1 →`pCount[1] +=1`→ pCount[1]=1
2	s[2] = a → 索引0 →`sCount[0] +=1`→ sCount[0]=1	p[2] = c → 索引2 →`pCount[2] +=1`→ pCount[2]=1