🎯 问题描述（来源于LeetCode）

描述：给你一个二进制数组 nums，你可以在其中删除至多一个元素。请你返回删除一个元素后，数组中全为 1 的最长子数组的长度。
说明：如果数组全是 1，你必须删除一个，所以结果要减 1。

  • 示例：
    • 示例 1： 
      1
      2
      3
      输入: nums = [1,1,0,1]
      输出: 3
      解释: 删除下标 2 的 0，得到 [1,1,1]。
    • 示例 2： 
      1
      2
      3
      输入: nums = [1,1,1]
      输出: 2
      解释: 必须删除一个 1，结果为 [1,1]。

💻 解题思路

思路：滑动窗口 (Sliding Window)

  1. 维护窗口：维护一个窗口，使其最多包含 1 个 0。
  2. 移动指针：
    • right 指针遍历数组，将元素加入窗口。
    • 如果窗口内 0 的数量超过 1，则移动 left 指针收缩窗口。
  3. 更新答案：在窗口合法时，利用 Counter 直接获取窗口内 1 的数量更新最大值。
  4. 边界处理：如果最大长度等于数组长度，说明全是 1，必须减 1。

思路1：代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        count = Counter()
        ans = 0
        left = 0
        
        for right, num in enumerate(nums):
            count[num] += 1 # 扩展窗口
            
            # 收缩窗口：保证最多只有 1 个 0
            while count[0] > 1:
                count[nums[left]] -= 1 # 修复后的关键点
                left += 1
            
            # 因为 count 是精准的窗口计数器，count[1] 是有效的
            ans = max(ans, count[1])
        
        # 特殊情况处理：全为 1 时必须删一个
        if ans == len(nums):
            return ans - 1
        return ans

思路1：📊 性能分析

  • 时间复杂度：O(n)O(n)。每个元素最多被 right 访问一次，被 left 访问一次。
  • 空间复杂度：O(1)O(1)。Counter 最多存储两个键值对 (0 和 1)，空间是常数级的。

思考

  1. 为什么现在 count[1] 能用了？
    核心在于 count[nums[left]] -= 1。这行代码保证了 count 字典永远只记录当前窗口内的数据。此时 count[1] 就是窗口内 1 的真实数量。
  2. 两种写法的取舍：
    虽然 count[1] 在逻辑上是通的，但在工程实践中，(right - left + 1) - count[0] 通常更受青睐。因为计算 (right - left + 1) 是 O(1)O(1) 的算术运算，而访问 count[1] 涉及哈希表查找（虽然极快，但理论上比加减法慢）。不过，在这道题中，两者的性能差异几乎可以忽略不计。