java如何定义滑动

定义滑动窗口的基本概念

滑动窗口是一种用于处理数组或列表数据的算法技巧，通过维护一个动态的窗口（通常是子数组或子序列），在遍历数据时高效地更新窗口范围以解决问题。适用于子数组求和、最长子串、最小覆盖子串等场景。

实现滑动窗口的步骤

1. 初始化窗口边界和关键变量
定义窗口的左右指针（如left和right），初始通常设为0。根据问题需求初始化辅助变量（如最大值、最小值或哈希表）。

int left = 0, right = 0;
int maxLength = 0;
Map<Character, Integer> windowMap = new HashMap<>();

2. 移动右指针扩展窗口
通过循环移动右指针，逐步将元素纳入窗口，并更新相关状态（如计数、和等）。

while (right < s.length()) {
    char c = s.charAt(right);
    windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);
    right++;
    // 更新状态或检查条件
}

3. 收缩左指针优化窗口
当窗口满足某些条件时（如和超过目标值或出现重复字符），移动左指针缩小窗口，同时更新状态。

while (windowMap.get(c) > 1) {
    char leftChar = s.charAt(left);
    windowMap.put(leftChar, windowMap.get(leftChar) - 1);
    left++;
}

4. 更新结果
在每次窗口变化后，根据问题需求记录结果（如最大长度、最小窗口等）。

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

示例代码：无重复字符的最长子串

public 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);
        window.put(c, window.getOrDefault(c, 0) + 1);
        right++;

        while (window.get(c) > 1) {
            char leftChar = s.charAt(left);
            window.put(leftChar, window.get(leftChar) - 1);
            left++;
        }

        maxLen = Math.max(maxLen, right - left);
    }
    return maxLen;
}

关键点

• 窗口定义：明确窗口内维护的数据含义（如字符频率、数值和）。
• 边界移动条件：右指针用于探索数据，左指针用于优化窗口。
• 复杂度：通常为O(n)，每个元素最多被访问两次。

通过调整窗口的扩展和收缩逻辑，可以解决不同变种的滑动窗口问题。