首页/资讯中心/详情

滑动窗口算法解决LeetCode 1004最长连续1问题

滑动窗口算法解决LeetCode 1004最长连续1问题
📅 发布时间：2026/8/4 3:40:23

1. 题目解析与核心思路

这道LeetCode 1004题"Max Consecutive Ones III"是一个典型的滑动窗口问题。题目要求我们找到一个二进制数组中，在最多翻转K个0的情况下，能够获得的最长连续1的子数组长度。

举个例子，给定数组[1,1,1,0,0,0,1,1,1,1,0]和K=2，我们可以翻转两个0变成1，得到的最长连续1子数组长度是6（翻转索引5和6的0）。

1.1 问题本质理解

这道题的核心在于理解"翻转"操作的实际含义。在实际编程中，我们并不需要真正修改数组元素，而是通过统计窗口内0的个数来判断是否满足条件。当窗口内0的个数不超过K时，窗口可以继续扩展；否则需要收缩窗口左边界。

1.2 滑动窗口算法选择

滑动窗口算法是解决这类子数组/子串问题的高效方法，时间复杂度为O(n)，空间复杂度为O(1)。相比暴力解法O(n^2)的时间复杂度，滑动窗口能显著提升性能。

2. C语言实现详解

2.1 基础变量定义

int longestOnes(int* nums, int numsSize, int k) { int left = 0, right = 0; int max_len = 0; int zero_count = 0; }
  • left和right分别表示窗口的左右边界
  • max_len记录当前找到的最大长度
  • zero_count统计当前窗口内0的个数

2.2 主循环逻辑

for (; right < numsSize; right++) { if (nums[right] == 0) { zero_count++; } while (zero_count > k) { if (nums[left] == 0) { zero_count--; } left++; } max_len = fmax(max_len, right - left + 1); }

循环中关键点：

  1. 右指针right不断右移扩展窗口
  2. 遇到0时增加zero_count
  3. 当zero_count超过K时，移动左指针left直到zero_count不大于K
  4. 每次循环更新最大长度

2.3 边界条件处理

  • 空数组：需要在函数开始处检查numsSize是否为0
  • K=0的情况：退化为寻找最长连续1子数组
  • 全1数组：直接返回数组长度
  • K大于等于数组长度：直接返回数组长度

3. 算法优化与变种

3.1 早期终止优化

当剩余未处理的元素数量加上当前窗口长度不超过已找到的max_len时，可以提前终止循环：

if (max_len >= numsSize - left) { break; }

3.2 最大可能窗口优化

可以记录数组中0的总数，如果K大于等于总0数，直接返回数组长度：

int total_zeros = 0; for (int i = 0; i < numsSize; i++) { if (nums[i] == 0) total_zeros++; } if (k >= total_zeros) return numsSize;

3.3 变种问题思考

  1. 如果要求返回具体的子数组而非长度？
  2. 如果数组元素不是0/1而是任意数字？
  3. 如果允许的翻转操作不是固定K次而是有不同代价？

4. 性能分析与测试用例

4.1 时间复杂度分析

  • 最佳情况：O(n) - 当数组全为1时只需遍历一次
  • 最坏情况：O(2n) - 每个元素最多被左右指针各访问一次
  • 平均情况：O(n)

4.2 空间复杂度

仅使用固定数量的变量，空间复杂度为O(1)

4.3 测试用例设计

// 测试用例1: 常规情况 int nums1[] = {1,1,1,0,0,0,1,1,1,1,0}; assert(longestOnes(nums1, 11, 2) == 6); // 测试用例2: K=0 int nums2[] = {1,0,1,1,0,1}; assert(longestOnes(nums2, 6, 0) == 2); // 测试用例3: 全1数组 int nums3[] = {1,1,1,1}; assert(longestOnes(nums3, 4, 1) == 4); // 测试用例4: K大于0的总数 int nums4[] = {0,0,1,0}; assert(longestOnes(nums4, 4, 5) == 4);

5. 常见错误与调试技巧

5.1 指针移动顺序错误

常见错误是在收缩窗口时先移动左指针再减少zero_count，正确的顺序应该是：

// 错误示例 while (zero_count > k) { left++; if (nums[left] == 0) zero_count--; } // 正确写法 while (zero_count > k) { if (nums[left] == 0) zero_count--; left++; }

5.2 窗口长度计算错误

窗口长度应该是right - left + 1而非right - left，因为数组索引从0开始。

5.3 边界条件遗漏

容易忽略K=0或K大于等于数组长度的情况，导致不必要的计算或错误结果。

5.4 调试技巧

  1. 打印窗口变化过程：
printf("left=%d, right=%d, zeros=%d, max=%d\n", left, right, zero_count, max_len);

  1. 使用小规模测试用例手动验证

  2. 检查循环不变式：确保每次循环后zero_count始终表示窗口[left, right]内0的个数

6. 实际应用场景

这类滑动窗口算法在实际开发中有广泛应用：

  1. 网络流量分析：检测特定时间段内的异常流量
  2. 用户行为分析：寻找连续活跃用户序列
  3. 金融交易监控：识别可疑的交易模式
  4. 视频流处理：寻找最佳的视频片段
  5. 基因组序列分析：查找特定模式的DNA序列

7. 扩展学习建议

  1. 类似题目练习：

      1. Longest Repeating Character Replacement
      1. Longest Substring Without Repeating Characters
      1. Minimum Size Subarray Sum

  2. 算法优化方向：

    • 尝试用双指针的不同实现方式
    • 思考如何扩展到二维数组
    • 考虑并行化处理的可能性

  3. 实际工程应用：

    • 学习如何将算法封装为可重用组件
    • 思考如何处理流式数据(无法一次性加载全部数据)
    • 了解分布式环境下的滑动窗口实现

在实际编码面试中，这类问题考察的重点不仅是写出正确的代码，还包括：

  • 能否清晰解释算法思路
  • 能否分析时间/空间复杂度
  • 能否考虑边界条件和异常情况
  • 能否进行代码优化和性能调优