这个最长的1s子数组删除一个元素后出了什么问题

Question

我正在尝试解决LeetCode问题1493。删除一个元素后最长的 1 子数组:

给定一个二进制数组

nums

，您应该从中删除一个元素。

返回结果数组中仅包含

1

的最长非空子数组的大小。如果不存在这样的子数组，则返回

0

。

思考过程

在数组开头使用

i

和

j

应用滑动窗口机制：

• 如果

  array[j]

  不为0，我们会继续递增

  j

  ，因为
是安全的
• 如果

  array[j]

  为 0 并且这是第一次 0，我们仍然会增加

  j

  ，因为这样是安全的，并且增加

  count0

• 如果

  array[j]

  是0并且是第二次0，如果

  array[i]

  是0，那么我们减少计数并增加

  i

• 如果

  array[j]

  是0并且是第二次0，如果

  array[i]

  不为0，那么我们只增加

  i

我的代码

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] #expected 2
[1,1,0,1] #expected 3
[0,1,1,1,0,1,1,0,1] #expected 5

问题

我的代码没有返回任何正确答案。对于上面列出的三个测试用例，它返回 3、4 和 6。

我的错误是什么？

Answer 1

你的算法很好，但挑战要求你应该返回结果数组中的大小（仅包含1的最长非空子数组）。您已返回其在 original 数组中的大小。由于需要在找到的子数组中删除一项，因此您应该比当前少返回一项：

toReturn = max(toReturn, j-i - 1)  # One less!

您可以通过避免

i

仅以步骤 1 来加速代码。因为您已经知道它必须在哪里继续执行直到遇到零，所以 and 您已经遇到了该零之前使用

j

索引时，当您遇到

j

时，您可以跟踪该索引，并让

i

一次性“跳转”到该已保存的索引。

对于零频率明显小于 1 频率的数组，您将受益于使用

index

方法来查找下一个零所在的位置。

这是这个想法的实现：

class Solution:
    def longestSubarray(self, array: List[int]) -> int:
        n = len(array)
        i = -1 # Index of a zero that is imagined in front of the array
        array.append(0)  # Add a dummy zero at the end
        j = array.index(0)
        toReturn = j - 1
        while j < n:  # As long as there are more zeroes...
            k = j  # Keep track of the current zero
            j = array.index(0, k + 1)  # ...and find the next one
            toReturn = max(toReturn, j - i - 2)
            i = k  # Have i "jump" to the next zero after it.
        return toReturn