Python滑动窗口求最长全1子数组时触发KeyError:0报错

算法题要求：给定仅由0和1组成的数组，最多允许将k个0替换为1，求数组中全为1的最长连续子数组长度。
给出示例：输入Array=[0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1]，k=2时，输出为6；原因为替换索引5、8位置的0后，可得到长度为6的最长全1连续子数组。

def length_of_longest_substring(arr, k):
    '''
    Create a hashmap that records the values of 0 and 1, initialize them to 0. Do a sliding 
    window.
    WHILE the frequency of 0 is greater than k, subtract arr[windowStart] from HM and then 
    increment 
    wS.
    Use the max function to record longest substring length. Return that.
    '''

    hm = {'0': '0', '1': '0'}
    (windowStart, longest) = (0, 0)
    for windowEnd in range(len(arr)):
        right = arr[windowEnd]
        hm[right] = hm.get(right, 0) + 1
        while hm["0"] > k:
            hm[arr[windowStart]] -= 1
            windowStart += 1
        longest = max(longest, windowEnd - windowStart + 1)
    return longest


def main():
    print(length_of_longest_substring([1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1], 2)) 
    #Return 6
    print(length_of_longest_substring([1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1], 3))
    #Return 9
main()

运行上述代码时，执行到while hm["0"] > k:语句时抛出KeyError: 0的错误。测试将哈希表初始键值改为整数0后代码可正常运行，尝试使用hm.get("0")方法取值仍出现相同报错。

• 字典键类型不匹配：输入数组中的元素是整数类型的0和1，但初始化字典时使用的是字符串类型的'0'、'1'作为键。Python字典的键匹配严格校验数据类型，整数0和字符串"0"是完全独立的两个键，不存在关联。
• 初始值类型错误：字典中两个字符串键对应的初始值是字符串'0'，不是数值0，即使键匹配成功，字符串类型也无法参与数值比较、加减运算，会触发类型错误。
• 逻辑错位：遍历窗口右边界时，代码一直用数组里的整数作为键更新计数，相当于给字典新增了整数0、整数1的键值对，初始定义的两个字符串键从未被更新；当代码尝试读取整数0的键值时，在窗口第一次遇到元素0之前，字典中不存在这个键，就会抛出KeyError。

首先修正字典的键和值类型，保证和数组元素类型一致，修正后的代码如下：

def length_of_longest_substring(arr, k):
    # 键使用整数0、1，初始值为数值0，和数组元素类型匹配
    hm = {0: 0, 1: 0}
    window_start, longest = 0, 0
    for window_end in range(len(arr)):
        right_val = arr[window_end]
        hm[right_val] += 1
        # 窗口内0的数量超过可替换上限时，收缩左边界
        while hm[0] > k:
            left_val = arr[window_start]
            hm[left_val] -= 1
            window_start += 1
        longest = max(longest, window_end - window_start + 1)
    return longest


def main():
    print(length_of_longest_substring([1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1], 2)) 
    # 输出6
    print(length_of_longest_substring([1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1], 3))
    # 输出9
main()

优化版本 #

由于逻辑中只需要统计窗口内0的个数，不需要记录1的计数，可以直接用单个变量实现，代码更简洁，开销更低：

def length_of_longest_substring(arr, k):
    window_start, longest, zero_count = 0, 0, 0
    for window_end in range(len(arr)):
        if arr[window_end] == 0:
            zero_count += 1
        while zero_count > k:
            if arr[window_start] == 0:
                zero_count -= 1
            window_start += 1
        longest = max(longest, window_end - window_start + 1)
    return longest

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