BISHI116　【模板】双指针¶

中等通过率 18.74%python3样例通过牛客 AC双指针

一句话

找出所有「元素两两不同」的最长区间。

解题思路¶

这题考什么¶

最经典的「无重复字符最长子串」双指针，外加一步「把所有最长区间都列出来」。

维护 last[v] = 值 v 最近一次出现的下标。右端点 r 从左往右扫，左端点 l 只会单调右移：当 a[r] 在 [l, r-1] 中出现过时，直接把 l 跳到 last[a[r]] + 1。每个下标各被 l、r 扫过一次，O(n)。

第二步的关键结论：对每个 r，以 r 结尾的合法区间里最长的那个是唯一的，即 [lo(r), r]。若某个长度为 best 的合法区间 [l, r] 存在，则必有 lo(r) <= l 且 r - lo(r) + 1 <= best，两边一夹得 l = lo(r)。所以「所有最长区间」= {(lo(r), r) : r - lo(r) + 1 == best}，每个 r 至多贡献一个。

数据规模与复杂度¶

n <= 2e5，O(n) 时间、O(n) 空间（a_i <= n，用数组当哈希表）。

坑在哪¶

题面明说没有 SPJ，必须按 l 递增输出。由于 lo(r) 在长度相同时随 r 严格递增，按 r 从小到大输出天然满足；
a_i 的范围是 0..n（含 0），last 数组要开 n+1 长；
答案区间至少有一个（单个元素总是合法），不必特判空；
输出量最大 2e5 行，用 "\n".join 一次性写出。

参考实现¶

solutions/BISHI116.py
import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = list(map(int, data[1:1 + n]))
    # 值域是 0..n，用定长数组当哈希表，比 dict 快且省内存
    last = [-1] * (n + 1)                    # a_i ∈ [0, n]；-1 表示该值还没出现过
    lo = [0] * n                             # lo[r] = 以 r 结尾的最长合法区间左端（0-indexed）
    l = 0                                    # 当前窗口左端，全程只增不减
    best = 0
    # ---- 第一遍：双指针求出每个 r 对应的 lo[r]，同时记下全局最长长度 ----
    for r in range(n):
        v = a[r]
        j = last[v]
        if j >= l:                           # v 在窗口内出现过，左端跳过去
            l = j + 1                        # 跳到重复位置的右边，一步到位而不是逐格挪
        last[v] = r                          # 更新前先用旧值，顺序不能反
        lo[r] = l
        if r - l + 1 > best:
            best = r - l + 1
    # ---- 第二遍：长度等于 best 的 (lo[r], r) 就是一个答案区间 ----
    # r 从小到大扫，lo[r] 也随之递增，输出天然按 l 递增（本题没有 SPJ，顺序必须对）
    out = []
    push = out.append
    for r in range(n):
        if r - lo[r] + 1 == best:
            push("%d %d" % (lo[r] + 1, r + 1))   # 内部 0-indexed，输出转回 1-indexed
    sys.stdout.write("%d\n%s\n" % (len(out), "\n".join(out)))


main()

BISHI116 【模板】双指针¶