滑动窗口

滑动窗口算法是一种高效解决数组/字符串子区间问题的技巧，通过维护一个动态窗口来避免重复计算，时间复杂度通常为 O(n)。其核心思想是：

1. 双指针维护窗口：左指针 left 和右指针 right 定义窗口边界
2. 右指针扩展窗口：当窗口满足条件时，右指针向右移动
3. 左指针收缩窗口：当窗口不满足条件时，左指针向右移动
4. 实时更新结果：在窗口移动过程中记录最优解

问题 1：最大连续 1 的个数

问题描述

给定一个二进制数组 nums，计算其中最大连续 1 的个数。

示例：

输入: [1,1,0,1,1,1]
输出: 3
解释: 开头的两位和最后的三位都是连续 1，所以最大连续 1 的个数是 3。

算法思路

单次遍历计数：

1. 遍历数组，使用计数器 count 记录当前连续 1 的数量
2. 遇到 1 时：count++ 并更新最大值
3. 遇到 0 时：重置 count = 0
4. 遍历结束后返回记录的最大值

滑动窗口优化（双指针）：

1. 使用 left 指针标记当前连续序列的起点
2. 右指针 right 遍历数组：
   • 遇到 1：继续扩展窗口
   • 遇到 0：将左指针移动到当前 0 的下一个位置
3. 实时计算窗口长度 right - left + 1 并更新最大值

代码实现

方法一：计数法（推荐）

class Solution {
    /**
     * 计算最大连续1的个数（计数法）
     * 
     * @param nums 二进制数组
     * @return 最大连续1的个数
     */
    public int findMaxConsecutiveOnes(int[] nums) {
        int maxCount = 0;    // 记录最大值
        int count = 0;       // 当前连续1计数器
        
        for (int num : nums) {
            if (num == 1) {
                count++;            // 遇到1增加计数
                maxCount = Math.max(maxCount, count);  // 更新最大值
            } else {
                count = 0;          // 遇到0重置计数器
            }
        }
        return maxCount;
    }
}

方法二：双指针法（滑动窗口）

class Solution {
    /**
     * 计算最大连续1的个数（双指针法）
     * 
     * @param nums 二进制数组
     * @return 最大连续1的个数
     */
    public int findMaxConsecutiveOnes(int[] nums) {
        int left = 0;        // 窗口左边界
        int maxLen = 0;      // 记录最大长度
        
        for (int right = 0; right < nums.length; right++) {
            // 遇到0时，左边界跳到下一个位置（跳过0）
            if (nums[right] == 0) {
                left = right + 1;
            }
            // 更新窗口长度（即使遇到0，窗口长度=0不影响最大值）
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

算法分析

• 时间复杂度：O(n)，只需遍历数组一次
• 空间复杂度：O(1)，仅使用常数空间
• 两种方法对比：
  • 计数法：逻辑更简洁直观，效率高
  • 双指针法：展示滑动窗口思想，为更复杂问题打基础

测试用例

public static void main(String[] args) {
    Solution solution = new Solution();
    
    // 测试用例1：常规情况
    int[] nums1 = {1,1,0,1,1,1};
    System.out.println("Test 1: " + solution.findMaxConsecutiveOnes(nums1)); // 3
    
    // 测试用例2：全1数组
    int[] nums2 = {1,1,1,1};
    System.out.println("Test 2: " + solution.findMaxConsecutiveOnes(nums2)); // 4
    
    // 测试用例3：全0数组
    int[] nums3 = {0,0,0,0};
    System.out.println("Test 3: " + solution.findMaxConsecutiveOnes(nums3)); // 0
    
    // 测试用例4：开头结尾连续1
    int[] nums4 = {1,0,1,1,0,1,1,1,1};
    System.out.println("Test 4: " + solution.findMaxConsecutiveOnes(nums4)); // 4
    
    // 测试用例5：单元素数组
    int[] nums5 = {1};
    System.out.println("Test 5: " + solution.findMaxConsecutiveOnes(nums5)); // 1
    
    // 测试用例6：空数组
    int[] nums6 = {};
    System.out.println("Test 6: " + solution.findMaxConsecutiveOnes(nums6)); // 0
}

关键点

1. 计数器重置时机：遇到 0 时立即重置计数器
2. 实时更新最大值：每次遇到 1 都要检查是否刷新记录
3. 边界处理：
   • 空数组返回 0
   • 全 0 数组返回 0
   • 单元素数组返回元素值（0 或 1）
4. 双指针特性：
   • 左指针只在遇到 0 时跳跃
   • 窗口长度计算包含当前右指针位置

常见问题

1. 为什么双指针法中遇到 0 时要设置 left = right + 1？

   • 这样保证窗口内不含 0，因为：
     • 当 nums[right]=0 时，窗口为 [right+1, right]（空窗口）
     • 下次循环 right++ 后，窗口变为 [right+1, right+1]（单元素窗口）

2. 计数法和双指针法哪个更好？

   • 计数法更简洁高效，双指针法展示了滑动窗口思想，为处理更复杂问题（如包含翻转操作）奠定基础。

3. 如何处理全 1 数组？

   • 计数器会持续累加直到结束，最终返回数组长度。

扩展：返回最长连续 1 的起止位置

public int[] findMaxConsecutiveOnesRange(int[] nums) {
    int maxStart = 0, maxEnd = 0; // 记录最长序列起止位置
    int start = 0;                // 当前序列起始位置
    int maxLen = 0;               // 记录最大长度
    
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 1) {
            // 遇到1：检查是否刷新记录
            int currentLen = i - start + 1;
            if (currentLen > maxLen) {
                maxLen = currentLen;
                maxStart = start;
                maxEnd = i;
            }
        } else {
            // 遇到0：重置起始位置（下一个位置）
            start = i + 1;
        }
    }
    return new int[]{maxStart, maxEnd};
}

问题 2：最大连续 1 的个数 II

问题描述

给定一个二进制数组 nums，计算其中最大连续 1 的个数，最多可以翻转一个 0（即将一个 0 变成 1）。

示例：

输入: [1,0,1,1,0]
输出: 4
解释: 翻转第一个 0，可以得到连续 4 个 1。

算法思路

双指针滑动窗口：

1. 维护窗口内 0 的计数 zeroCount
2. 当 zeroCount > 1 时收缩左边界
3. 实时更新最大窗口长度

优化方法（记录前一个 0 的位置）：

1. 用 prevZero 记录上一个 0 的位置
2. 当遇到新 0 时，将左边界移动到 prevZero + 1
3. 更新 prevZero 为当前 0 的位置

代码实现

方法一：滑动窗口（通用解法）

class Solution {
    /**
     * 计算最多翻转一个0后的最大连续1个数
     * 
     * @param nums 二进制数组
     * @return 最大连续1的个数
     */
    public int findMaxConsecutiveOnes(int[] nums) {
        int left = 0;        // 窗口左边界
        int maxLen = 0;      // 记录最大长度
        int zeroCount = 0;   // 窗口内0的计数
        
        for (int right = 0; right < nums.length; right++) {
            // 遇到0时增加计数
            if (nums[right] == 0) {
                zeroCount++;
            }
            
            // 当0的数量超过1时收缩左边界
            while (zeroCount > 1) {
                if (nums[left] == 0) {
                    zeroCount--;
                }
                left++;
            }
            
            // 更新最大窗口长度
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

方法二：记录前一个 0 的位置（优化解法）

class Solution {
    /**
     * 优化解法：记录前一个0的位置
     * 
     * @param nums 二进制数组
     * @return 最大连续1的个数
     */
    public int findMaxConsecutiveOnes(int[] nums) {
        int left = 0;        // 窗口左边界
        int maxLen = 0;      // 记录最大长度
        int prevZero = -1;   // 记录前一个0的位置
        
        for (int right = 0; right < nums.length; right++) {
            // 遇到0时处理
            if (nums[right] == 0) {
                // 如果之前有0，左边界移动到前一个0之后
                if (prevZero != -1) {
                    left = prevZero + 1;
                }
                prevZero = right;  // 更新前一个0的位置
            }
            
            // 更新最大窗口长度
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

算法分析

• 时间复杂度：O(n)
  • 两种方法都只需遍历数组一次
• 空间复杂度：O(1)
  • 仅使用常数空间
• 方法对比：
  • 滑动窗口：通用性强，可扩展至翻转 k 个 0 的情况
  • 优化解法：效率更高（无内层循环），专为翻转一个 0 设计

算法过程

输入：nums = [1,0,1,1,0]

1. 滑动窗口法：

   • right=0：1 → maxLen=1
   • right=1：0 → zeroCount=1 → maxLen=2
   • right=2：1 → maxLen=3
   • right=3：1 → maxLen=4
   • right=4：0 → zeroCount=2
     • 收缩：left 移动到2 → zeroCount=1
     • maxLen=4（窗口[2,4]）

2. 优化解法：

   • prevZero=-1, left=0
   • right=0：1 → maxLen=1
   • right=1：0 → prevZero=1
   • right=2：1 → maxLen=3（窗口[0,2]）
   • right=3：1 → maxLen=4（窗口[0,3]）
   • right=4：0 → left=prevZero+1=2 → prevZero=4
   • maxLen=4（窗口[2,4]）

测试用例

public static void main(String[] args) {
    Solution solution = new Solution();
    
    // 测试用例1：标准示例
    int[] nums1 = {1,0,1,1,0};
    System.out.println("Test 1: " + solution.findMaxConsecutiveOnes(nums1)); // 4
    
    // 测试用例2：全1数组
    int[] nums2 = {1,1,1,1};
    System.out.println("Test 2: " + solution.findMaxConsecutiveOnes(nums2)); // 4
    
    // 测试用例3：全0数组
    int[] nums3 = {0,0,0,0};
    System.out.println("Test 3: " + solution.findMaxConsecutiveOnes(nums3)); // 1
    
    // 测试用例4：多个0间隔
    int[] nums4 = {1,0,1,0,1,0,1};
    System.out.println("Test 4: " + solution.findMaxConsecutiveOnes(nums4)); // 3
    
    // 测试用例5：单元素
    int[] nums5 = {0};
    System.out.println("Test 5: " + solution.findMaxConsecutiveOnes(nums5)); // 1
    
    // 测试用例6：空数组
    int[] nums6 = {};
    System.out.println("Test 6: " + solution.findMaxConsecutiveOnes(nums6)); // 0
    
    // 测试用例7：长序列
    int[] nums7 = {1,1,0,1,1,1,0,1,1,1};
    System.out.println("Test 7: " + solution.findMaxConsecutiveOnes(nums7)); // 7
}

关键点

1. 翻转机制：

   • 允许将一个 0 视为 1
   • 本质是寻找最多包含一个 0 的最长连续子数组

2. 滑动窗口核心：

   • 维护窗口内 0 的数量
   • zeroCount > 1 时收缩左边界

3. 优化解法核心：

   • prevZero 记录前一个 0 的位置
   • 遇到新 0 时，左边界跳到 prevZero + 1

4. 边界处理：

   • 全 0 数组：可翻转一个 0 → 长度为 1
   • 单元素数组：最小长度为元素值（0→1，1→1）

常见问题

1. 为什么优化解法中遇到 0 时要移动左边界？

   • 当遇到第二个 0 时，第一个 0 的翻转权被"让给"当前 0，所以左边界移动到第一个 0 之后。

2. 两种方法哪个更好？

   • 优化解法效率更高（无内层循环），但滑动窗口通用性更强（可扩展至最多翻转 k 个 0）。

3. 如何处理连续多个 0 的情况？

   • 滑动窗口法会持续收缩直到 zeroCount≤1；优化解法会将左边界移动到上一个 0 之后，确保窗口最多包含一个 0。

问题 3：最大连续 1 的个数 III

问题描述

给定一个二进制数组 nums 和一个整数 k，如果最多可以将 k 个 0 翻转为 1，返回数组中连续 1 的最大个数。

算法思路

滑动窗口（双指针）：

1. 使用双指针 left 和 right 表示窗口的左右边界
2. 维护 zeroCount 记录窗口中 0 的数量
3. 右指针主动扩展窗口：
   • 遇到 1 直接扩展
   • 遇到 0 时，若 zeroCount < k 仍可扩展
4. 当 0 的数量超过 k 时，左指针收缩窗口：
   • 左边界遇到 0 时减少计数
5. 实时更新最大窗口长度（即连续 1 的最大长度）

代码实现

class Solution {
    /**
     * 查找最多翻转k个0后的最大连续1长度
     * 
     * @param nums 二进制数组
     * @param k 最多可翻转的0的数量
     * @return 最大连续1的长度
     */
    public int longestOnes(int[] nums, int k) {
        int left = 0;       // 窗口左指针
        int maxLen = 0;     // 记录最大长度
        int zeroCount = 0;  // 窗口内0的计数
        
        // 右指针遍历整个数组
        for (int right = 0; right < nums.length; right++) {
            // 遇到0时增加计数（相当于需要翻转）
            if (nums[right] == 0) {
                zeroCount++;
            }
            
            // 当0的数量超过k时，收缩左边界
            while (zeroCount > k) {
                // 左边界遇到0时减少计数
                if (nums[left] == 0) {
                    zeroCount--;
                }
                left++;  // 左指针右移
            }
            
            // 更新最大窗口长度（此时窗口满足条件）
            maxLen = Math.max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
}

算法分析

• 时间复杂度：O(n)
  • 每个元素最多被访问两次（左指针和右指针各一次）
• 空间复杂度：O(1)
  • 仅使用常数级别的额外空间

算法过程

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2

1. 初始化：left=0, maxLen=0, zeroCount=0
2. 窗口移动过程：
   • right=0-2：连续1，maxLen=3
   • right=3：遇到0，zeroCount=1，maxLen=4
   • right=4：遇到0，zeroCount=2，maxLen=5
   • right=5：遇到0，zeroCount=3>k
     • 收缩：left 移动到4（移除1个0），zeroCount=2
   • right=6-9：连续1，maxLen=6（窗口[4,9]）
   • right=10：遇到0，zeroCount=3>k
     • 收缩：left 移动到5（移除1个0），zeroCount=2
3. 最终结果：6

测试用例

public static void main(String[] args) {
    Solution solution = new Solution();
    
    // 测试用例1：标准示例
    int[] nums1 = {1,1,1,0,0,0,1,1,1,1,0};
    int k1 = 2;
    System.out.println("Test 1: " + solution.longestOnes(nums1, k1)); // 6
    
    // 测试用例2：全1数组
    int[] nums2 = {1,1,1,1,1};
    int k2 = 2;
    System.out.println("Test 2: " + solution.longestOnes(nums2, k2)); // 5
    
    // 测试用例3：全0数组
    int[] nums3 = {0,0,0,0};
    int k3 = 2;
    System.out.println("Test 3: " + solution.longestOnes(nums3, k3)); // 2
    
    // 测试用例4：k=0（不能翻转）
    int[] nums4 = {1,0,1,1,0};
    int k4 = 0;
    System.out.println("Test 4: " + solution.longestOnes(nums4, k4)); // 2
    
    // 测试用例5：k足够大（可翻转所有0）
    int[] nums5 = {1,0,1,0,1,0,1};
    int k5 = 3;
    System.out.println("Test 5: " + solution.longestOnes(nums5, k5)); // 7
    
    // 测试用例6：空数组
    int[] nums6 = {};
    int k6 = 2;
    System.out.println("Test 6: " + solution.longestOnes(nums6, k6)); // 0
}

关键点

1. 窗口扩张条件：
   • 右指针无条件向右移动
   • 遇到0时增加计数，只要 zeroCount <= k 窗口就有效
2. 窗口收缩触发：
   • 当 zeroCount > k 时启动收缩
   • 左指针移动到移除足够0的位置
3. 结果更新时机：
   • 每次右指针移动后更新
   • 此时窗口保证满足条件（zeroCount <= k）
4. 边界处理：
   • 空数组直接返回0
   • k=0时退化为普通连续1问题

常见问题

1. 为什么用 while 而不是 if？

   • 左指针可能需要多次移动才能满足条件（如连续多个0的情况）

2. k=0 时如何处理？

   • 当遇到0时必须立即收缩窗口，退化为标准连续1问题

3. k 大于数组长度会怎样？

   • 窗口永远不会收缩，直接返回数组长度

4. 为什么不在收缩前更新结果？

   • 收缩前窗口可能无效（zeroCount > k），收缩后才满足条件

扩展：返回翻转位置

如需返回具体翻转位置，可记录最佳窗口的起止索引：

int bestLeft = 0, bestRight = 0;
// ...
if (right - left + 1 > maxLen) {
    maxLen = right - left + 1;
    bestLeft = left;
    bestRight = right;
}
// 返回翻转位置（bestLeft到bestRight之间的0）

总结：

1. 适用场景：

   • 子数组/子字符串问题
   • “满足条件的最长/最短连续子序列”
   • 如：最大连续1、最小覆盖子串、无重复子串等

2. 算法框架：

int left = 0, right = 0;
while (right < n) {
    // 1. 扩展右边界并更新状态
    // 2. 检查是否满足收缩条件
    while (窗口需要收缩) {
        // 3. 收缩左边界并更新状态
        left++;
    }
    // 4. 更新最优解
}

3. 优化：
   • 合理设计窗口状态（计数、哈希表等）
   • 精确控制收缩条件
   • 避免重复计算（通过哈希表直接跳转边界）