# 滑动窗口与前缀和算法实战：从子数组和到最小覆盖子串
## 引言：双指针思想的两种经典范式
在处理数组和字符串相关问题时，滑动窗口和前缀和是两种高效且优雅的算法范式。它们都以双指针技术为基础，却服务于不同类型的问题场景。滑动窗口擅长处理连续子区间的最优解问题，而前缀和则专注于快速计算子数组的累积值。本文将通过从基础的"和为K的子数组"到复杂的"最小覆盖子串"问题，深入探讨这两种算法的实现原理和应用技巧。
## 前缀和：快速计算子数组和的利器
前缀和的核心思想是通过预处理，将子数组和的计算复杂度从O(n)降低到O(1)。先看一个基础示例：
```java
// 前缀和基础实现
public class PrefixSum {
// 计算数组的前缀和
public static int[] calculatePrefixSum(int[] nums) {
int n = nums.length;
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
return prefix;
}
// 利用前缀和快速计算子数组和
public static int subarraySum(int[] prefix, int left, int right) {
// 计算nums[left...right]的和，包含两端
return prefix[right + 1] - prefix[left];
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5};
int[] prefix = calculatePrefixSum(nums);
// 计算子数组nums[1...3]的和：2+3+4=9
System.out.println("子数组和: " + subarraySum(prefix, 1, 3));
}
}
```
## 和为K的子数组：前缀和的进阶应用
这是前缀和算法的经典应用场景，需要统计和为特定值的子数组个数：
```java
// 和为K的子数组个数
public class SubarraySumEqualsK {
public static int countSubarrays(int[] nums, int k) {
// 使用哈希表记录前缀和出现的次数
Map<Integer, Integer> prefixSumCount = new HashMap<>();
prefixSumCount.put(0, 1); // 前缀和为0的情况
int count = 0;
int currentSum = 0;
for (int num : nums) {
currentSum += num;
// 如果存在前缀和等于currentSum - k，
// 说明存在子数组的和为k
if (prefixSumCount.containsKey(currentSum - k)) {
count += prefixSumCount.get(currentSum - k);
}
// 更新当前前缀和出现的次数
prefixSumCount.put(currentSum,
prefixSumCount.getOrDefault(currentSum, 0) + 1);
}
return count;
}
public static void main(String[] args) {
int[] nums = {1, 1, 1, 2, -1, 1};
int k = 3;
System.out.println("和为" + k + "的子数组个数: " +
countSubarrays(nums, k));
}
}
```
这个算法的时间复杂度为O(n)，空间复杂度为O(n)，关键在于理解`currentSum - k`的含义：当前前缀和减去目标值K，得到的就是需要寻找的之前某个前缀和。
## 滑动窗口：处理连续子区间问题的模板
滑动窗口算法适用于寻找满足特定条件的连续子区间问题：
```java
// 滑动窗口算法框架
public class SlidingWindowTemplate {
public static void slidingWindowTemplate(String s, String t) {
// 需要维护的窗口状态
Map<Character, Integer> window = new HashMap<>();
Map<Character, Integer> need = new HashMap<>();
// 初始化need：记录目标字符及其出现次数
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0; // 记录窗口中满足need条件的字符个数
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++;
}
}
// 判断左侧窗口是否要收缩
while (window需要收缩的条件) {
// d是将移出窗口的字符
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);
}
}
}
}
}
```
## 最小覆盖子串：滑动窗口的经典难题
这是滑动窗口算法中最 具挑战性的问题之一，需要在源字符串中找到包含目标字符串所有字符的最小子串：
```java
// 最小覆盖子串实现
public class MinimumWindowSubstring {
<"gre.j9k5.org.cn"><"otr.j9k5.org.cn"><"rth.j9k5.org.cn">
public static String minWindow(String s, String t) {
if (s == null || t == null || s.length() < t.length()) {
return "";
}
// 记录目标字符串的字符需求
Map<Character, Integer> need = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
// 滑动窗口的状态
Map<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
int valid = 0; // 窗口中满足need条件的字符数
// 记录最小覆盖子串的起始位置和长度
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++;
}
}
// 当窗口已包含t的所有字符时，尝试收缩左边界
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);
}
public static void main(String[] args) {
String s = "ADOBECODEBANC";
String t = "ABC";
System.out.println("最小覆盖子串: " + minWindow(s, t));
// 输出: "BANC"
}
}
```
这个算法的时间复杂度为O(n)，其中n是源字符串s的长度。关键在于维护两个哈希表和valid计数器，确保窗口始终包含目标字符串的所有字符。
## 算法对比与应用场景分析
虽然滑动窗口和前缀和都基于双指针思想，但它们的应用场景有明显差异：
**前缀和适用场景：**
1. 需要频繁计算子数组和的场景
2. 处理"和为K"类型的计数问题
3. 二维矩阵中的子矩阵和计算
4. 需要快速范围查询的情况
**滑动窗口适用场景：**
1. 寻找满足条件的最短/最长连续子数组
2. 字符串匹配和包含关系问题
3. 固定窗口大小的统计问题
4. 需要维护窗口内部状态的问题
## 实战技巧与常见陷阱
在实现这两种算法时，需要注意以下关键点：
```java
// 滑动窗口的常见优化技巧
public class SlidingWindowOptimizations {
// 技巧1：使用数组替代哈希表（当字符集有限时）
public static String minWindowArray(String s, String t) {
int[] need = new int[128]; // ASCII字符集
int[] window = new int[128];
for (char c : t.toCharArray()) {
need[c]++;
}
int left = 0, right = 0;
int count = 0; // 窗口中满足条件的字符数
int minLen = Integer.MAX_VALUE;
int start = 0;
while (right < s.length()) {
char c = s.charAt(right);
right++;
if (need[c] > 0) {
window[c]++;
if (window[c] <= need[c]) {
count++;
}
}
while (count == t.length()) {
if (right - left < minLen) {
minLen = right - left;
start = left;
}
char d = s.charAt(left);
left++;
if (need[d] > 0) {
if (window[d] <= need[d]) {
count--;
}
window[d]--;
}
}
}
return minLen == Integer.MAX_VALUE ? "" :
s.substring(start, start + minLen);
}<"mg.j9k5.org.cn"><"uhj.j9k5.org.cn"><"sef.j9k5.org.cn">
// 技巧2：处理包含重复字符的场景
public static int lengthOfLongestSubstring(String s) {
Map<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
int maxLen = 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);
}
maxLen = Math.max(maxLen, right - left);
}
return maxLen;
}
}
```
## 总结：算法思想与实际应用的结合
滑动窗口和前缀和算法体现了计算机科学中"空间换时间"和"预处理"的重要思想。通过深入理解这两种算法，我们不仅能够解决具体的编程问题，更能培养出优化算法、分析复杂度的思维能力。
在实际开发中，这两种算法的应用远不止于算法题目。滑动窗口可用于实时数据处理、流式分析等场景；前缀和则在统计、数据分析等领域有广泛应用。掌握它们的核心原理和实现技巧，能够帮助我们在面对复杂问题时，快速识别适用模式并设计出高效解决方案。
无论是准备技术面试还是解决实际工程问题，滑动窗口和前缀和都是值得深入掌握的算法工具。通过反复练习和总结，我们能够将这些算法内化为解决问题的直觉，在面对新的挑战时游刃有余。
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/19545/viewspace-3109497/ ，如需转载，请注明出处，否则将追究法律责任。
