Advent of Code 2022 Day6 Part2优化代码失效问题排查

任务背景 #

给定输入字符串，需返回检测到首个消息起始标记前处理的字符数量。消息起始标记定义为输入中长度为14的无重复字符子串的最后一个字符索引。例如，若寻找长度为3的子串，输入abababc应返回6——因为出现c时，首次得到长度为3的无重复子串abc，其最后一个字符的索引为6。

问题代码 #

以下代码在测试用例中有效，但真实输入返回None：

def part2V2(inputLine):
    INPUT_LINE = inputLine.strip()
    chars = [False] * 26
    OFFSET = ord('a')
    LENGTH = len(INPUT_LINE)

    i = 0

    for j in range(LENGTH):
        index = ord(INPUT_LINE[j]) - OFFSET

        if chars[index] == False:
            chars[index] = True

            if j-i == 13: #13 since we are looking for 14 unique characters minus 1 for the index
                return j
        else:
            chars = [False] * 26
            chars[index] = True
            i = j

问题原因 #

1. 重复字符的窗口重置逻辑错误 #

当遇到重复字符时，代码直接将窗口左边界i跳到当前j的位置，并重置整个chars数组。但实际上，重复字符可能出现在窗口的中间位置，而非起始位置。例如输入abcdeafghijklm，当j指向第二个a时，正确的窗口左边界应该移动到第一个a的下一位（i=1），而非直接跳到j的位置。原逻辑会丢弃窗口中间的有效字符，导致永远无法凑齐14个无重复字符，循环结束后没有返回值，最终返回None。

2. 测试用例巧合命中错误逻辑 #

测试用例abababc中，重复字符都出现在窗口起始位置附近，原代码的错误逻辑刚好能符合预期结果，但真实输入的字符分布更复杂，暴露了逻辑缺陷。

修复方案 #

使用正确的滑动窗口逻辑：维护窗口内的字符计数，当遇到重复字符时，逐步移动左边界直到窗口内无重复字符，再检查窗口长度是否达标。

def part2V2(inputLine):
    input_line = inputLine.strip()
    char_count = [0] * 26
    offset = ord('a')
    left = 0

    for right, char in enumerate(input_line):
        idx = ord(char) - offset
        char_count[idx] += 1

        # 移除窗口内的重复字符，直到当前字符计数为1
        while char_count[idx] > 1:
            left_char_idx = ord(input_line[left]) - offset
            char_count[left_char_idx] -= 1
            left += 1

        # 检查窗口长度是否达到14
        if right - left + 1 == 14:
            return right  # 按你的需求返回最后一个字符的索引，若需返回字符数量则返回 right + 1

    # 若未找到标记（按题目要求不会出现），返回-1或按需处理
    return -1

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