BM92　最长无重复子数组¶

中等通过率 29.8%python3核心代码模式样例通过牛客 AC数组哈希双指针

一句话

滑动窗口配一张「值 -> 最后出现位置」的哈希表。

解题思路¶

这题考什么¶

要找最长的、元素互不相同的连续子数组。暴力枚举左右端点是 O(n^2)。关键是单调性：窗口 [l, r] 内部无重复时，它的任何子区间也无重复；反过来，一旦 r 右移引入了一个已在窗口里的值，左端 l 只能往右走、绝不会往左退。左右指针各自单调前进，这正是滑动窗口成立的前提。见双指针与滑动窗口。

用字典 last 记录每个值最近一次出现的下标。右端 r 从 0 扫到 n-1：

若 arr[r] 在 last 中，且 last[arr[r]] >= l
    说明这个值就落在当前窗口内 -> 把 l 直接跳到 last[arr[r]] + 1
last[arr[r]] = r
ans = max(ans, r - l + 1)

左界一步跳到重复元素的下一格，而不是逐格右移：中间那些位置作为左端点时，窗口里必然还含着那个重复值，一个都不可能成立，可以整段跳过。

手推 [1,2,3,1,2,3,2,2]：

r=0 值1  l=0  窗口 [1]        len=1
r=1 值2  l=0  窗口 [1,2]      len=2
r=2 值3  l=0  窗口 [1,2,3]    len=3   <- 答案
r=3 值1  last[1]=0 >= 0 -> l=1  窗口 [2,3,1]  len=3
r=4 值2  last[2]=1 >= 1 -> l=2  窗口 [3,1,2]  len=3
r=5 值3  last[3]=2 >= 2 -> l=3  窗口 [1,2,3]  len=3
r=6 值2  last[2]=4 >= 3 -> l=5  窗口 [3,2]    len=2
r=7 值2  last[2]=6 >= 5 -> l=7  窗口 [2]      len=1

数据规模与复杂度¶

n <= 1e5，元素满足 0 < arr[i] <= 1e5，时限「其他语言 2 秒」。 l 与 r 各自只前进 n 步，时间 O(n)；空间 O(n)——哈希表最多存下 n 个互不相同的值。暴力枚举左右端点再判重是 O(n^2) = 1e10 次操作，Python 下差着好几个数量级。

坑在哪¶

last[v] >= left 这个判断不能省，它是整题唯一的陷阱。字典里存的是全局最后一次出现的位置，很可能是早已被窗口甩在身后的旧记录。不比较就无脑把左界拉过去，l 会往回退，窗口里重新混进重复元素，长度也会算大。加上这个判断，l 全程单调不减。手推里 r=6 那一步正是分水岭：last[2]=4 仍在窗口内（4 >= 3），必须收；若此时窗口左界已经在 5 之后，那条记录就是过期的，收了反而退回去。
last[v] 的更新要放在收缩左界之后。先写 last[v] = r 再判断，比较的就成了刚写进去的 r 与 left，永远成立，左界会被一路推到 r+1。
窗口长度是 r - l + 1（闭区间两端都算），少了这个 +1 每个答案都短一格。
空数组直接返回 0：循环一次都不进，ans 保持初值，不必特判。

参考实现¶

solutions/nowcoder/BM92/sol.py
from typing import List, Optional


class Solution:
    def maxLength(self, arr: List[int]) -> int:
        last = {}          # 值 -> 该值最后一次出现的下标（全局记录，未必在窗口内）
        left = 0           # 当前窗口的左端，闭区间；只前进不后退
        ans = 0            # 空数组时循环不进入，直接返回 0
        for right, v in enumerate(arr):
            # 只有旧位置仍落在窗口内才需要收缩左界；否则那是早已滑出窗口的过期记录，
            # 照它跳会把左界往回拉，窗口里重新混进重复元素
            if v in last and last[v] >= left:
                left = last[v] + 1      # 一步跳到重复元素的下一格，中间的左端点都不可能成立
            last[v] = right             # 必须在收缩之后更新，否则比较的是刚写进去的自己
            # 窗口是闭区间，长度为 right - left + 1
            if right - left + 1 > ans:
                ans = right - left + 1
        return ans

BM92 最长无重复子数组¶