LeetCode 1493题错误排查：删除一个元素后的最长1子数组

问题背景 #

题目要求：给定二进制数组nums，删除一个元素后，返回仅含1的最长非空子数组的长度，若无则返回0。

你采用滑动窗口思路实现的代码如下：

class Solution:
    def longestSubarrayOf1s(self, array):
        i,j = 0,0
        N = len(array)
        toReturn,count0,curr_count=0,0,0
        while j < N:
            if array[j] == 1:
                j+=1
            else:
                if count0 == 0:
                    j+=1
                    count0+=1
                else:
                    if array[i] == 0:
                        i+=1
                        count0-=1
                    else:
                        i+=1
            print('i am updating my max answer to ', j-i, 'in the window of ', i, j)
            toReturn = max(toReturn, j-i)
        return toReturn

测试用例问题 #

• 输入[1,1,1]：预期2，返回3
• 输入[1,1,0,1]：预期3，返回4
• 输入[0,1,1,1,0,1,1,0,1]：预期5，返回6

错误原因分析 #

你的滑动窗口逻辑本身是在寻找最多包含1个0的最长子数组，但完全忽略了题目中必须删除一个元素的核心约束：

1. 当窗口全为1时，必须删除其中一个1，有效长度应为窗口长度-1，但你的代码直接返回窗口长度，导致全1数组结果错误。
2. 当窗口包含1个0时，删除这个0后的有效长度也是窗口长度-1，你的代码直接返回窗口长度，比正确结果多1。

简言之，你计算的是「最多含1个0的最长子数组长度」，而题目要求的是「删除一个元素后的最长全1子数组长度」，二者的关系是：后者 = 前者 - 1。

修正后的代码 #

只需在返回结果时，将窗口最大长度减1，同时确保结果不小于0（处理数组全为0或长度为1的边界情况）：

class Solution:
    def longestSubarray(self, array):
        i,j = 0,0
        N = len(array)
        max_window = 0
        count0 = 0
        while j < N:
            if array[j] == 1:
                j += 1
            else:
                if count0 == 0:
                    j += 1
                    count0 += 1
                else:
                    if array[i] == 0:
                        count0 -= 1
                    i += 1
            max_window = max(max_window, j - i)
        # 必须删除一个元素，结果为窗口长度-1，且不能小于0
        return max(max_window - 1, 0)

验证修正结果 #

• 输入[1,1,1]：max_window=3，返回3-1=2，符合预期
• 输入[1,1,0,1]：max_window=4，返回4-1=3，符合预期
• 输入[0,1,1,1,0,1,1,0,1]：max_window=6，返回6-1=5，符合预期

内容的提问来源于stack exchange，提问作者Karina