「一本通 2.1 练习 8」收集雪花

题目描述

有 $n$ 个时刻，每个时刻落下一片雪花，用非负整数 $x_i$ 表示形状。同学们从某个时刻 $a$ 开始、到某个时刻 $b$ 停止，收集 $a \sim b$ 之间的所有雪花，要求收集到的雪花形状互不相同。第一行输入正整数 $n$ ，第二行输入 $n$ 个非负整数；输出最多能收集的雪花数量。数据范围： $1 \leqslant n \leqslant 10^6$ ， $0 \leqslant x_i \leqslant 10^9$ 。样例：

text

思路

右指针向右扫描，用哈希表记录每个形状最近一次出现的下标；当当前形状上次出现在窗口内时，左端点直接跳到上次位置的下一位，左指针单调不降。答案取每一步窗口长度的最大值，总复杂度 $O(n)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 12:17
# update_at: 2026-10-04 11:22

import sys


def max_unique_subarray(seq: list[int]) -> int:
    """计算序列中最长无重复连续子区间的长度。

    使用双指针滑动窗口：
    维护当前窗口 [left, right]，用哈希表 last_pos 记录每个元素最后一次出现的下标。
    当元素再次出现时，左指针必须跳到其上次出现位置的下一个位置（注意不能回退）。
    """
    last_pos: dict[int, int] = {}
    left = 0
    ans = 0

    for right, val in enumerate(seq):
        if val in last_pos and last_pos[val] >= left:
            left = last_pos[val] + 1
        last_pos[val] = right
        ans = max(ans, right - left + 1)

    return ans


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    snows = [next(data) for _ in range(n)]
    print(max_unique_subarray(snows))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 00:18
 * update_at: 2026-10-06 00:18
 */

#include <cstdio>

typedef long long ll;

const int MAXN = 1e6 + 5;
const int HASH = 2097151; // 哈希表长度取 2^21 - 1，方便取模

// 由于雪花编号 x <= 1e9 开不下数组，用链地址法哈希表记录每个形状最近出现的位置
int head[HASH + 1]; // head[h] 表示哈希值为 h 的链表头，0 表示空（下标从 1 开始）
int nxt[MAXN];      // nxt[i] 表示哈希链表中第 i 条记录的下一条
ll val[MAXN];       // val[i] 表示第 i 条记录保存的雪花形状
ll pos_[MAXN];      // pos_[i] 表示形状 val[i] 最近一次出现的下标
ll a[MAXN];         // a[i] 表示第 i 个时刻落下的雪花形状
int cnt = 0;        // 已经用掉的记录条数

// 返回形状 x 在当前窗口内最近一次出现的位置，没出现过返回 0
ll find_last(ll x) {
    int h = (int)(x % HASH);
    for (int e = head[h]; e; e = nxt[e]) {
        if (val[e] == x)
            return pos_[e];
    }
    return 0;
}

// 把形状 x 最近出现的位置更新为 p
void update(ll x, ll p) {
    int h = (int)(x % HASH);
    for (int e = head[h]; e; e = nxt[e]) {
        if (val[e] == x) {
            pos_[e] = p;
            return;
        }
    }
    // 该形状第一次出现，新建一条记录挂在链表头上
    cnt++;
    val[cnt] = x;
    pos_[cnt] = p;
    nxt[cnt] = head[h];
    head[h] = cnt;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);

    int left = 1;   // 当前无重复窗口的左端点，单调不降
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ll p = find_last(a[i]);
        // 该形状在窗口内部出现过，左端点必须跳到上次出现位置的下一位
        if (p >= left)
            left = (int)p + 1;
        update(a[i], i);
        if (i - left + 1 > ans)
            ans = i - left + 1;
    }
    printf("%lld\n", ans);
    return 0;
}

「一本通 2.1 练习 8」收集雪花

目录

题目描述

思路

参考代码