滑动窗口
更新: 8/28/2025 字数: 0 字 时长: 0 分钟
无重复字符的最长子串
java
/**
* <p>此方法使用滑动窗口和哈希集合（{@link HashSet}）来找出不含有重复字符的最长子串的长度。</p>
* <p>滑动窗口通过两个指针 {@code left} 和 {@code right} 维护一个当前正在检查的子串，哈希集合用于高效地检查窗口内字符的重复性。</p>
*
* <h3>算法思路：</h3>
* <ol>
* <li>初始化变量：
* <ul>
* <li>{@code left = 0}：滑动窗口的左边界。</li>
* <li>{@code maxLength = 0}：记录找到的最长无重复字符子串的长度。</li>
* <li>{@code charSet = new HashSet<Character>()}：一个哈希集合，用于存储当前滑动窗口中的所有字符，以便快速判断字符是否重复。</li>
* </ul>
* </li>
* <li>使用一个 {@code right} 指针从字符串的左端（索引 {@code 0}）开始遍历到右端 {@code (n-1)}。{@code right} 指针代表滑动窗口的右边界。</li>
* <li>在每次 {@code right} 指针移动时，进行以下操作：
* <ul>
* <li><strong>检查重复：</strong> 如果 {@code charSet} 中已经包含 {@code s.charAt(right)}，说明当前字符与窗口内的某个字符重复。
* <ul>
* <li>此时，需要收缩窗口的左边界 {@code left}，直到窗口内不再包含重复字符。</li>
* <li>循环执行：从 {@code charSet} 中移除 {@code s.charAt(left)}，并递增 {@code left}，直到 {@code s.charAt(right)} 不再重复（即 {@code charSet} 中不再包含它）。</li>
* </ul>
* </li>
* <li><strong>添加字符并更新最大长度：</strong>
* <ul>
* <li>将 {@code s.charAt(right)} 添加到 {@code charSet} 中（此时窗口内已无重复字符）。</li>
* <li>更新 {@code maxLength = Math.max(maxLength, right - left + 1)}。{@code (right - left + 1)} 是当前无重复字符子串的长度。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li>{@code right} 指针继续向右移动，重复步骤 3。</li>
* <li>遍历结束后，返回 {@code maxLength}。</li>
* </ol>
*
* <h3>核心思想：</h3>
* <p>滑动窗口配合哈希集合的策略确保了窗口内始终没有重复字符。当遇到重复字符时，窗口的左边界会及时收缩，以维护无重复字符的特性。在每次有效扩展窗口右边界时，都会更新最长长度。</p>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(n)}。
* <ul>
* <li>{@code right} 指针从 {@code 0} 到 {@code n-1} 遍历一次。</li>
* <li>{@code left} 指针最多也从 {@code 0} 到 {@code n-1} 遍历一次。</li>
* <li>{@code HashSet} 的 {@code add}、{@code remove} 和 {@code contains} 操作平均时间复杂度为 {@code O(1)}。</li>
* <li>因此，总的时间复杂度为 {@code O(n)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(k)}，其中 {@code k} 是字符集的大小（例如，对于 ASCII 字符集，{@code k = 128}；对于扩展 ASCII，{@code k = 256}）。
* <ul>
* <li>在最坏情况下，{@code HashSet} 中存储的字符数量不会超过字符集的大小。</li>
* <li>如果字符集非常大或者字符是 Unicode 字符，那么 {@code k} 可能会很大，但对于常见字符集，可以认为是常数。</li>
* </ul>
* </li>
* </ul>
*
* @param s 输入的字符串。
* @return 不含有重复字符的最长子串的长度。
*/
public int lengthOfLongestSubstring(String s) {
int n = s.length();
if (n == 0) {
return 0;
}
int maxLength = 0;
int left = 0; // 滑动窗口左边界
Set<Character> charSet = new HashSet<>(); // 存储窗口内字符
// right 指针遍历字符串
for (int right = 0; right < n; right++) {
// 如果 charSet 中已包含当前字符 s.charAt(right)
// 说明出现重复，需要收缩窗口左边界
while (charSet.contains(s.charAt(right))) {
charSet.remove(s.charAt(left)); // 从集合中移除最左边的字符
left++; // 左边界右移
}
// 此时窗口内无重复字符，将当前字符加入集合
charSet.add(s.charAt(right));
// 更新最大长度
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}java
/**
* <p>此方法使用滑动窗口和哈希表（{@link HashMap} 或 {@link int[]}) 来找出不含有重复字符的最长子串的长度。</p>
* <p>相比于 {@link HashSet}，{@link HashMap} 可以存储字符及其在字符串中出现的最新索引，这有助于更高效地调整窗口左边界。</p>
*
* <h3>算法思路：</h3>
* <ol>
* <li>初始化变量：
* <ul>
* <li>{@code left = 0}：滑动窗口的左边界。</li>
* <li>{@code maxLength = 0}：记录找到的最长无重复字符子串的长度。</li>
* <li>{@code charIndexMap = new HashMap<Character, Integer>()}：一个哈希表，存储窗口中每个字符及其在字符串中<strong>最新出现</strong>的索引。</li>
* </ul>
* </li>
* <li>使用一个 {@code right} 指针从字符串的左端（索引 {@code 0}）开始遍历到右端 {@code (n-1)}。{@code right} 指针代表滑动窗口的右边界。</li>
* <li>在每次 {@code right} 指针移动时，进行以下操作：
* <ul>
* <li><strong>检查重复：</strong> 如果 {@code charIndexMap} 中已经包含 {@code s.charAt(right)}，并且这个重复字符的最新索引 {@code charIndexMap.get(s.charAt(right))} 在当前窗口的左边界 {@code left} 之后（即 {@code >= left}）：
* <ul>
* <li>这意味着当前字符与窗口内的某个字符重复。</li>
* <li>此时，滑动窗口的左边界 {@code left} 需要跳到重复字符的下一个位置。</li>
* <li>更新 {@code left = Math.max(left, charIndexMap.get(s.charAt(right)) + 1)}。使用 {@code Math.max} 是为了避免 {@code left} 指针回退（如果新的重复字符的索引在旧 {@code left} 之前，我们不应该让 {@code left} 回退）。</li>
* </ul>
* </li>
* <li><strong>更新字符索引并更新最大长度：</strong>
* <ul>
* <li>将当前字符 {@code s.charAt(right)} 及其索引 {@code right} 存入或更新到 {@code charIndexMap} 中。</li>
* <li>更新 {@code maxLength = Math.max(maxLength, right - left + 1)}。{@code (right - left + 1)} 是当前无重复字符子串的长度。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li>{@code right} 指针继续向右移动，重复步骤 3。</li>
* <li>遍历结束后，返回 {@code maxLength}。</li>
* </ol>
*
* <h3>核心思想：</h3>
* <p>通过 {@link HashMap} 存储字符及其最新索引，当遇到重复字符时，可以直接将窗口左边界跳到重复字符的下一个位置，而无需像 {@link HashSet} 方法那样逐个移除左侧字符，从而简化了窗口收缩的逻辑。</p>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(n)}。
* <ul>
* <li>{@code right} 指针从 {@code 0} 到 {@code n-1} 遍历一次。</li>
* <li>{@code HashMap} 的 {@code put}、{@code get} 和 {@code containsKey} 操作平均时间复杂度为 {@code O(1)}。</li>
* <li>每次迭代中的操作都是常数时间。</li>
* <li>因此，总的时间复杂度为 {@code O(n)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(k)}，其中 {@code k} 是字符集的大小（例如，对于 ASCII 字符集，{@code k = 128}；对于扩展 ASCII，{@code k = 256}）。
* <ul>
* <li>{@code HashMap} 中存储的字符数量不会超过字符集的大小。</li>
* <li>对于 ASCII 字符集，可以使用一个大小为 128 或 256 的 {@code int[]} 数组来替代 {@link HashMap}，将字符的 ASCII 值作为数组索引，进一步优化常数因子。</li>
* </ul>
* </li>
* </ul>
*
* @param s 输入的字符串。
* @return 不含有重复字符的最长子串的长度。
*/
public int lengthOfLongestSubstring(String s) {
int n = s.length();
if (n == 0) {
return 0;
}
int maxLength = 0;
int left = 0; // 滑动窗口左边界
// 存储字符及其在字符串中出现的最新索引
// 例如：'a' -> 3 表示字符 'a' 最新出现在索引 3
Map<Character, Integer> charIndexMap = new HashMap<>();
// right 指针遍历字符串
for (int right = 0; right < n; right++) {
char currentChar = s.charAt(right);
// 如果 charIndexMap 中已包含当前字符，并且其索引 >= left
// 说明当前字符与窗口内的某个字符重复了
if (charIndexMap.containsKey(currentChar) && charIndexMap.get(currentChar) >= left) {
// 将窗口左边界移动到重复字符的下一个位置
// 例如 "abba", 当 right = 3 (第二个 'a') 时，charIndexMap.get('a') = 0.
// 此时 left=2, charIndexMap.get('a') (0) < left (2), 不会更新 left.
// 而是当 charIndexMap.get(currentChar) >= left 时才更新。
// 实际上 for "abca", right=3 (第二个 a), map{'a':0,'b':1,'c':2}.
// charIndexMap.get('a')=0, left=0. 'a'重复。left = Math.max(0, 0+1) = 1.
left = charIndexMap.get(currentChar) + 1;
}
// 更新当前字符的最新索引
charIndexMap.put(currentChar, right);
// 更新最大长度
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}找到字符串中所有字母异位词
java
/**
* <p>此方法使用滑动窗口和两个字符计数数组来找到字符串 {@code s} 中所有 {@code p} 的异位词子串的起始索引。</p>
* <p>核心思想是维护一个长度与 {@code p} 相同的滑动窗口，并比较窗口内字符的频率与 {@code p} 中字符的频率是否一致。</p>
*
* <h3>算法思路：</h3>
* <ol>
* <li><strong>预处理与边界检查：</strong>
* <ul>
* <li>获取字符串 {@code s} 和 {@code p} 的长度，分别为 {@code sLen} 和 {@code pLen}。</li>
* <li>如果 {@code sLen < pLen}，则 {@code s} 中不可能包含 {@code p} 的异位词，直接返回空列表。</li>
* <li>初始化一个结果列表 {@code result} 来存储所有符合条件的异位词子串的起始索引。</li>
* <li>创建两个大小为 26 的整数数组 {@code sCount} 和 {@code pCount}。
* <ul>
* <li>{@code pCount} 用于存储模式字符串 {@code p} 中每个小写字母的出现频率。</li>
* <li>{@code sCount} 用于存储当前滑动窗口中每个小写字母的出现频率。</li>
* <li>数组索引 {@code 0} 到 {@code 25} 分别对应字符 {@code 'a'} 到 {@code 'z'}。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>初始化第一个滑动窗口：</strong>
* <ul>
* <li>遍历字符串 {@code p} 的所有字符，计算并填充 {@code pCount} 数组。</li>
* <li>遍历字符串 {@code s} 的前 {@code pLen} 个字符（即构建第一个滑动窗口），计算并填充 {@code sCount} 数组。</li>
* </ul>
* </li>
* <li><strong>检查第一个窗口：</strong>
* <ul>
* <li>使用 {@code Arrays.equals(pCount, sCount)} 比较两个频率数组。如果它们完全相同，说明 {@code s} 的第一个子串 (从索引 0 开始，长度为 {@code pLen}) 是 {@code p} 的异位词。</li>
* <li>将起始索引 {@code 0} 添加到 {@code result} 列表中。</li>
* </ul>
* </li>
* <li><strong>滑动窗口并检查后续窗口：</strong>
* <ul>
* <li>使用一个循环，变量 {@code i} 从 {@code pLen} 开始遍历到 {@code sLen - 1}。{@code i} 代表当前滑动窗口的<strong>右边界</strong>（即新加入窗口的字符的索引）。</li>
* <li>在每次循环中，执行以下操作来滑动窗口：
* <ul>
* <li><strong>窗口扩展：</strong> 将新字符 {@code s.charAt(i)} 计入 {@code sCount}，即 {@code sCount[s.charAt(i) - 'a']++}。</li>
* <li><strong>窗口收缩：</strong> 将旧字符 {@code s.charAt(i - pLen)} (当前窗口最左边的字符) 从 {@code sCount} 中移除，即 {@code sCount[s.charAt(i - pLen) - 'a']--}。</li>
* </ul>
* </li>
* <li><strong>检查当前窗口：</strong> 再次使用 {@code Arrays.equals(pCount, sCount)} 比较两个频率数组。如果相等，说明当前滑动窗口对应的子串是 {@code p} 的异位词。</li>
* <li>将当前窗口的起始索引 {@code (i - pLen + 1)} 添加到 {@code result} 列表中。</li>
* </ul>
* </li>
* <li>所有循环结束后，返回存储所有异位词子串起始索引的 {@code result} 列表。</li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(sLen + pLen)}。
* <ul>
* <li>初始化 {@code pCount} 和第一个 {@code sCount} 需要 {@code O(pLen)} 时间。</li>
* <li>滑动窗口主循环执行 {@code sLen - pLen} 次。在每次迭代中，对频率数组的更新是常数时间 (两次数组访问和加减操作)。{@code Arrays.equals()} 比较两个长度为 26 的数组，也是常数时间 {@code O(26)}。</li>
* <li>因此，总时间复杂度为 {@code O(pLen + (sLen - pLen) * 26)}，简化为 {@code O(sLen + pLen)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>使用了两个大小为 26 的整数数组 ({@code sCount} 和 {@code pCount})，其大小是固定的常数，与输入字符串长度无关。</li>
* <li>结果列表的空间取决于找到的异位词数量，最坏情况下可能接近 {@code O(sLen)}，但通常不将其计入算法本身的额外空间复杂度。</li>
* </ul>
* </li>
* </ul>
*
* @param s 目标字符串。
* @param p 模式字符串，用于查找其异位词。
* @return 字符串 {@code s} 中所有 {@code p} 的异位词子串的起始索引列表。
*/
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
int sLen = s.length();
int pLen = p.length();
// 1. 边界条件判断：如果 s 的长度小于 p 的长度，不可能找到 p 的异位词
if (sLen < pLen) {
return result;
}
// 2. 创建两个频率数组，用于记录 p 中字符的频率和当前滑动窗口中字符的频率
// 数组大小为 26，对应小写字母 'a' 到 'z'
int[] sCount = new int[26];
int[] pCount = new int[26];
// 3. 初始化 pCount 和第一个滑动窗口 (s 的前 pLen 个字符) 的 sCount
for (int i = 0; i < pLen; i++) {
sCount[s.charAt(i) - 'a']++; // 统计 s 中第一个窗口的字符频率
pCount[p.charAt(i) - 'a']++; // 统计 p 中所有字符的频率
}
// 4. 检查第一个滑动窗口是否为 p 的异位词
// 如果两个频率数组完全相同，说明是异位词
if (Arrays.equals(pCount, sCount)) {
result.add(0); // 将第一个窗口的起始索引 0 加入结果列表
}
// 5. 滑动窗口：从第二个窗口开始，直到 s 的末尾
// i 指针代表滑动窗口的右边界
for (int i = pLen; i < sLen; i++) {
// 窗口向右滑动：
// 移入新字符：将 s.charAt(i) 加入当前窗口，其频率加 1
sCount[s.charAt(i) - 'a']++;
// 移出旧字符：将 s.charAt(i - pLen) (即当前窗口最左边的字符) 移除，其频率减 1
sCount[s.charAt(i - pLen) - 'a']--;
// 检查当前窗口 (即以 i - pLen + 1 为起始索引的子串) 是否为 p 的异位词
if (Arrays.equals(pCount, sCount)) {
// 如果是异位词，则将当前窗口的起始索引加入结果列表
// 当前窗口的起始索引是 (i - pLen + 1)
result.add(i - pLen + 1);
}
}
return result;
}贡献者
LI SIR