滑动窗口

什么是滑动窗口？

滑动窗口是一种动态调整区间范围的算法。它将问题中的“窗口”定义为一段连续的子数组或子字符串，并通过增加或减少窗口的左右边界来动态计算结果。窗口的范围会随着问题的需求而“滑动”，从而优化问题求解过程。它是一种高效的算法思想，广泛应用于数组和字符串问题，特别是涉及子数组、子字符串、窗口内统计等场景。

它的重要性在于：

1. 提升效率：通过动态调整窗口范围，避免暴力枚举所有可能的子区间，从而将时间复杂度从 $O(N^2)$ 或更高优化到 $O(N)$
2. 简化逻辑：滑动窗口提供了一个统一的框架，可以直观地处理许多问题，如最大/最小子数组和、子数组个数统计等。
3. 实际应用广泛：在数据流、字符串处理、窗口内最值计算等领域具有广泛应用。

核心思想

滑动窗口的核心思想是：通过一对指针（通常为左右指针 left 和 right），定义一个“窗口”，然后在窗口内进行动态计算。

实现步骤：

1. 初始化窗口：定义窗口的起点（left）和终点（right），一般初始为 0。
2. 扩展窗口：通过移动 right 指针扩展窗口，直到窗口内满足特定条件。
3. 缩小窗口：当窗口满足条件时，移动 left 指针缩小窗口，同时更新结果。
4. 重复上述过程：直到 right 指针遍历完整个数组或字符串。

关键点：

• 动态调整窗口的范围。
• 记录窗口内的状态（如当前和、频率计数等）。
• 根据问题需求判断何时更新结果。

滑动窗口的逻辑可以归纳为以下模板：

 public int slidingWindow(int[] nums, int target) {
	int left = 0, current_sum = 0, result = Integer.MAX_VALUE;
	for (int right = 0; right < nums.length; ++right) {
		current_sum += nums[right];  // 扩展窗口
		// 符合条件，尝试缩小窗口
		while (current_sum >= target) {
			result = Math.min(result, right - left + 1);
			current_sum -= nums[left++];  // 移动左边界，缩小窗口
		}
	}
	return result == Integer.MAX_VALUE ? 0 : result;  // 如果没找到满足条件的子数组返回 0
}

滑动窗口的应用场景

1. 求解固定长度的子数组/子字符串问题：
   • 如最大或最小子数组和，最长不重复子字符串。
2. 求解动态条件的区间问题：
   • 如满足条件的最短子数组，窗口内的元素个数统计。
3. 在线算法和数据流问题：
   • 滑动窗口可以在数据流中实时计算指标。

算法问题

无重复字符的最长子串

力扣-3. 无重复字符的最长子串

import java.util.HashSet;
import java.util.Set;

public class Code3 {
    public static void main(String[] args) {
        String s = "abcbcbb";
        System.out.println(lengthOfLongestSubstring(s));
    }

    public static int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int len = s.length();
        int right = 0;
        Set<Character> subSet = new HashSet<>();

        int max = 0;
        for (int i = 0; i < len; i++) {
            while(right < len && !subSet.contains(s.charAt(right))) {
                subSet.add(s.charAt(right));
                right++;
            }
            max = Math.max(max, subSet.size());
            subSet.remove(s.charAt(i));
        }
        return max;
    }
}

---

文章摘自 C++ 版本改为 Java 版本：https://cloud.tencent.com/developer/article/2480728