# 滑动窗口算法精解：从无重复字符到字母异位词匹配

## 引言：滑动窗口的算法哲学

滑动窗口算法以其简洁高效的特性，成为解决字符串和数组问题的利器。它通过维护一个动态的观察窗口，在遍历数据时智能地调整窗口边界，从而在不回溯的情况下找到最优解。本文将深入剖析滑动窗口在两类经典问题中的应用：无重复字符的最长子串和字母异位词匹配，揭示算法背后的统一思想。

## 无重复字符的最长子串：滑动窗口的入门典范

这是理解滑动窗口思想的绝佳起点。问题要求找到字符串中不包含重复字符的最长连续子串。

### 基础实现与算法分析

```java

// 无重复字符最长子串 - 基础实现

public class LongestSubstringWithoutRepeating {

public static int lengthOfLongestSubstring(String s) {

// 使用哈希集合记录窗口中的字符

Set<Character> window = new HashSet<>();

int left = 0; // 窗口左边界

int maxLength = 0;

for (int right = 0; right < s.length(); right++) {

char currentChar = s.charAt(right);

// 当发现重复字符时，收缩左边界

while (window.contains(currentChar)) {

window.remove(s.charAt(left));

left++;

}

// 将当前字符加入窗口

window.add(currentChar);

// 更新最大长度

maxLength = Math.max(maxLength, right - left + 1);

}

return maxLength;

}

public static void main(String[] args) {

String test1 = "abcabcbb";

String test2 = "bbbbb";

String test3 = "pwwkew";

System.out.println("测试 '" + test1 + "': " +

lengthOfLongestSubstring(test1)); // 应输出 3

System.out.println("测试 '" + test2 + "': " +

lengthOfLongestSubstring(test2)); // 应输出 1

System.out.println("测试 '" + test3 + "': " +

lengthOfLongestSubstring(test3)); // 应输出 3

}

```

这个实现的时间复杂度为O(n)，空间复杂度为O(min(n, m))，其中m是字符集大小。算法的关键在于当遇到重复字符时，持续收缩左边界直到重复字符被移除。

### 优化版本：使用数组加速查找

```java

// 优化版本：使用数组替代哈希集合

public class OptimizedLongestSubstring {

public static int lengthOfLongestSubstringOptimized(String s) {

// 假设字符集为ASCII，使用数组记录字符最后出现的位置

int[] lastIndex = new int[128];

Arrays.fill(lastIndex, -1); // 初始化为-1，表示未出现过

int maxLength = 0;

int left = 0; // 窗口左边界

for (int right = 0; right < s.length(); right++) {

char currentChar = s.charAt(right);

int charIndex = currentChar;

// 如果字符在当前窗口内出现过，更新左边界

if (lastIndex[charIndex] >= left) {

left = lastIndex[charIndex] + 1;

}

// 更新字符的最后出现位置

lastIndex[charIndex] = right;

// 计算当前窗口长度并更新最大值

maxLength = Math.max(maxLength, right - left + 1);

}

return maxLength;

}

```

优化版本通过记录每个字符最后出现的位置，避免了内层循环，将时间复杂度优化到严格的O(n)。

## 字母异位词匹配：滑动窗口的进阶应用

字母异位词是指字母相同但排列不同的字符串。滑动窗口可以高效地找到字符串中所有字母异位词的起始位置。

### 基础问题：找到所有异位词的起始索引

```java

// 找到字符串中所有字母异位词的起始位置

public class FindAllAnagrams {

public static List<Integer> findAnagrams(String s, String p) {

List<Integer> result = new ArrayList<>();

if (s.length() < p.length()) {

return result;

}

// 使用数组记录目标字符串的字符频率

int[] targetFreq = new int[26];

int[] windowFreq = new int[26];

// 初始化目标频率数组

for (int i = 0; i < p.length(); i++) {

targetFreq[p.charAt(i) - 'a']++;

}

// 初始化第一个窗口

for (int i = 0; i < p.length(); i++) {

windowFreq[s.charAt(i) - 'a']++;

}<"fbb.j9k5.org.cn"><"tbh.j9k5.org.cn"><"opj.j9k5.org.cn">

// 检查第一个窗口

if (Arrays.equals(targetFreq, windowFreq)) {

result.add(0);

}

// 滑动窗口遍历字符串

for (int i = p.length(); i < s.length(); i++) {

// 移除窗口最左边的字符

windowFreq[s.charAt(i - p.length()) - 'a']--;

// 添加新字符到窗口

windowFreq[s.charAt(i) - 'a']++;

// 检查当前窗口是否为异位词

if (Arrays.equals(targetFreq, windowFreq)) {

result.add(i - p.length() + 1);

}

return result;

}

public static void main(String[] args) {

String s = "cbaebabacd";

String p = "abc";

List<Integer> indices = findAnagrams(s, p);

System.out.println("字母异位词起始位置: " + indices);

// 应输出 [0, 6]

}

```

### 通用解决方案：维护有效字符计数

```java

// 使用有效字符计数的通用解法

public class AnagramsSlidingWindow {

public static List<Integer> findAnagramsUniversal(String s, String p) {

List<Integer> result = new ArrayList<>();

if (s.length() < p.length()) {

return result;

}

Map<Character, Integer> need = new HashMap<>();

Map<Character, Integer> window = new HashMap<>();

// 初始化需求表

for (char c : p.toCharArray()) {

need.put(c, need.getOrDefault(c, 0) + 1);

}

int left = 0, right = 0;

int valid = 0; // 记录窗口中满足需求的字符数量

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 >= p.length()) {

// 如果所有需求字符都满足条件

if (valid == need.size()) {

result.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 result;

}

```

## 算法模式对比与抽象

通过分析这两个问题，我们可以抽象出滑动窗口算法的通用模式：

```java

// 滑动窗口算法的通用模板

public class SlidingWindowTemplate {

<"efq.j9k5.org.cn"><"bft.j9k5.org.cn"><"ytm.j9k5.org.cn">

public static void slidingWindow(String s) {

// 初始化窗口数据结构

Map<Character, Integer> window = new HashMap<>();

int left = 0, right = 0;

while (right < s.length()) {

// 1. 扩大右边界

char c = s.charAt(right);

right++;

// 2. 更新窗口状态

updateWindowWhenExpand(c, window);

// 3. 判断是否需要收缩窗口

while (windowNeedShrink()) {

// 4. 收缩左边界

char d = s.charAt(left);

left++;

// 5. 更新窗口状态

updateWindowWhenShrink(d, window);

}

// 6. 更新结果（位置取决于具体问题）

updateResult();

}

private static void updateWindowWhenExpand(char c,

Map<Character, Integer> window) {

// 根据具体问题实现

}

private static boolean windowNeedShrink() {

// 根据具体问题实现

return false;

}

private static void updateWindowWhenShrink(char d,

Map<Character, Integer> window) {

// 根据具体问题实现

}

private static void updateResult() {

// 根据具体问题实现

}

```

## 实战应用：变种问题解析

### 问题1：最多替换K个字符的最长重复子串

```java

// 最多替换K个字符得到的最长重复子串

public class LongestRepeatingCharacterReplacement {

public static int characterReplacement(String s, int k) {

int[] charCount = new int[26];

int maxCount = 0; // 窗口内出现最多的字符次数

int maxLength = 0;

int left = 0;

for (int right = 0; right < s.length(); right++) {

char c = s.charAt(right);

charCount[c - 'A']++;

// 更新窗口内出现最多的字符次数

maxCount = Math.max(maxCount, charCount[c - 'A']);

// 如果窗口大小减去最大字符数大于k，需要收缩

while (right - left + 1 - maxCount > k) {

char leftChar = s.charAt(left);

charCount[leftChar - 'A']--;

left++;

}

maxLength = Math.max(maxLength, right - left + 1);

}

return maxLength;

}

```

### 问题2：包含所有字符的最短子串

```java

// 包含字符串t所有字符的最短子串

public class MinimumWindowSubstring {

public static String minWindow(String s, String t) {

if (s.length() < t.length()) return "";

Map<Character, Integer> need = new HashMap<>();

Map<Character, Integer> window = new HashMap<>();

for (char c : t.toCharArray()) {

need.put(c, need.getOrDefault(c, 0) + 1);

}

int left = 0, right = 0;

int valid = 0;

int start = 0, minLen = Integer.MAX_VALUE;

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 (valid == need.size()) {

if (right - left < minLen) {

start = left;

minLen = right - 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 minLen == Integer.MAX_VALUE ? "" :

s.substring(start, start + minLen);

}

```

## 算法性能分析与优化策略

滑动窗口算法的性能优化通常从以下几个方面考虑：

1. **数据结构选择**：根据字符集大小选择数组或哈希表

2. **状态维护**：避免每次重新计算窗口状态

3. **边界条件处理**：正确处理空字符串和边界情况

4. **提前终止**：在某些情况下可以提前结束遍历

## 总结：滑动窗口的思维模式

滑动窗口算法的精髓在于通过维护一个动态的观察区间，在遍历过程中不断调整窗口边界，从而高效地解决问题。从无重复字符的最长子串到字母异位词匹配，我们看到虽然问题形式不同，但核心思想相通。

掌握滑动窗口的关键在于：

1. 理解窗口扩张和收缩的条件

2. 学会维护窗口内部状态

3. 识别问题的滑动窗口特征

4. 根据具体问题选择合适的优化策略

在实际应用中，滑动窗口算法不仅可以解决字符串问题，还可以应用于数组、流数据处理等多个领域。通过不断练习和总结，我们能够将这种算法思维内化为解决复杂问题的直觉能力，在技术面试和实际开发中都能游刃有余。

滑动窗口算法体现了计算机科学中"局部观察，全局优化"的思想，通过对数据流的智能扫描，在不回溯的情况下找到最优解，这种高效性正是算法设计的魅力所在。

ITPub博客

滑动窗口算法精解：从无重复字符到字母异位词匹配

最新文章