Java滑动窗口实现详解
滑动窗口是一种常用的算法技巧,主要解决连续子数组/子字符串问题，以下是几种常见实现方式：
固定长度滑动窗口
public class FixedSlidingWindow {
// 示例：计算长度为k的子数组最大和
public static int maxSumWindow(int[] nums, int k) {
if (nums == null || nums.length < k) {
return 0;
}
// 计算第一个窗口的和
int windowSum = 0;
for (int i = 0; i < k; i++) {
windowSum += nums[i];
}
int maxSum = windowSum;
// 滑动窗口
for (int i = k; i < nums.length; i++) {
windowSum += nums[i] - nums[i - k]; // 加入新元素，移除旧元素
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
public static void main(String[] args) {
int[] nums = {1, 4, 2, 10, 23, 3, 1, 0, 20};
int k = 4;
System.out.println("最大和为: " + maxSumWindow(nums, k)); // 输出: 39
}
}
可变长度滑动窗口
public class VariableSlidingWindow {
// 示例：找出和大于等于target的最短子数组长度
public static int minSubArrayLen(int target, int[] nums) {
int left = 0;
int sum = 0;
int minLen = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right]; // 扩展窗口
// 收缩窗口
while (sum >= target) {
minLen = Math.min(minLen, right - left + 1);
sum -= nums[left];
left++;
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
public static void main(String[] args) {
int[] nums = {2, 3, 1, 2, 4, 3};
int target = 7;
System.out.println("最短子数组长度: " + minSubArrayLen(target, nums)); // 输出: 2
}
}
字符串滑动窗口通用模板
public class StringSlidingWindow {
// 通用模板：查找最长无重复字符子串
public static int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) return 0;
int left = 0;
int maxLen = 0;
Map<Character, Integer> charMap = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 如果字符已出现，移动左边界
if (charMap.containsKey(c) && charMap.get(c) >= left) {
left = charMap.get(c) + 1;
}
// 更新字符位置
charMap.put(c, right);
// 计算当前窗口长度
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
public static void main(String[] args) {
String s = "abcabcbb";
System.out.println("最长无重复子串长度: " + lengthOfLongestSubstring(s)); // 输出: 3
}
}
通用滑动窗口框架
public class SlidingWindowFramework {
// 滑动窗口通用模板
public static List<Integer> slidingWindowTemplate(int[] nums) {
List<Integer> result = new ArrayList<>();
if (nums == null || nums.length == 0) return result;
int left = 0, right = 0;
// 维护窗口状态的变量
int windowSum = 0;
int maxSum = Integer.MIN_VALUE;
while (right < nums.length) {
// 1. 扩展窗口：加入右边元素
int num = nums[right];
windowSum += num;
// 2. 根据条件收缩窗口
// 窗口长度固定为k
while (right - left + 1 > 3) { // 假设窗口最大长度为3
windowSum -= nums[left];
left++;
}
// 3. 更新结果
if (right - left + 1 == 3) {
maxSum = Math.max(maxSum, windowSum);
}
// 4. 继续移动右指针
right++;
}
result.add(maxSum);
return result;
}
}
实际应用示例：最小覆盖子串
public class MinWindowSubstring {
// 找出包含目标字符串所有字符的最小子串
public static String minWindow(String s, String t) {
if (s == null || t == null || 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; // 记录最小子串起始位置
int len = 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 < len) {
start = left;
len = 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 len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
public static void main(String[] args) {
String s = "ADOBECODEBANC";
String t = "ABC";
System.out.println("最小覆盖子串: " + minWindow(s, t)); // 输出: "BANC"
}
}
- 固定窗口：left和right同步移动，每次加入新元素并删除旧元素
- 可变窗口：right不断右移，当条件满足时左移left
- 关键变量：
- left/right：窗口边界
- window：窗口内数据状态
- valid：满足条件的计数
- result：记录最终结果
选择哪种实现取决于具体需求：固定长度问题用第一种，可变长度用第二种，字符串匹配用第三种。
