Unique Snowflakes

题意

给定一组整数序列，求其中没有重复数字的最长区间长度。

双指针,集合思想

暴力代码

        
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

        #include <iostream>
#include <set>
using namespace std;
const int maxn=2e6+5;
int n;
int a[maxn];

std::set<int> myset;


//暴力枚举以 a[j]为结尾的元素
void work() {
    int ans = 0;

    for(int j = 1;j <= n ;++j ) // j: 1->n
    {
        myset.clear();
        for(int i = j;i >= 1 ;--i ) // i: j->1
        {
            if( myset.find(a[i]) != myset.end() ) break;
            myset.insert(a[i]);
            if( ans < myset.size()) 
                ans = myset.size();
        }
    }
    std::cout << ans << "\n";
}

int main() {
    int T;
    std::cin >> T;
    while (T--) {
        std::cin >> n;
        for(int i = 1;i <= n ;++i ) // i: 1->n
        {
            std::cin >> a[i];
        }
        work();
    }
    
    return 0;
}

    

暴力优化

根据暴力代码进行优化,$f(j)$表示以j为结尾的不含有相同元素的连续区间$[i,j]$

• 那么$[i-1,j]$对于$f(j)$是没有贡献的,同样对$f(j+1)$也没有贡献
• 所以,可能对于$f(j+1)$贡献的区间是$[i,j+1]$
• 这具有单调性

        
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

        #include <iostream>
#include <set>
using namespace std;
const int maxn=2e6+5;
int n;
int a[maxn];

std::set<int> myset;


//暴力枚举以 a[j]为结尾的元素
void work() {
    int ans = 0;
    myset.clear();

    int i = 1;
    for(int j = 1;j <= n ;++j ) // j: 1->n
    {
        while( myset.find(a[j]) != myset.end() )
        {
            myset.erase(a[i]);
            i++;
        }
        myset.insert(a[j]);
        if( ans < myset.size())
            ans = myset.size();
        
    }
    std::cout << ans << "\n";
}

int main() {
    int T;
    std::cin >> T;
    while (T--) {
        std::cin >> n;
        for(int i = 1;i <= n ;++i ) // i: 1->n
        {
            std::cin >> a[i];
        }
        work();
    }
    return 0;
}

    

详细的证明: 反证法

这个证明可以通过**“反证法”（Proof by Contradiction）或者“最优性归纳”**（Optimality Induction）来完成。

为了让你更容易记忆和理解，我推荐使用**“反证法”**的逻辑。核心思想是：假设我们错过了一个更长的答案，推导出这个假设本身是不成立的。

证明目标

我们要证明：算法计算出的最大长度 max_len，一定等于全局的最长无重复区间长度。

证明过程

1. 定义标准答案

假设全局真正的最长无重复区间是 $[start, end]$（下标从 $start$ 到 $end$），其长度为 $Len_{opt}$。

2. 算法的行为

• 我们的右指针 $R$ 从 $0$ 遍历到 $N-1$。这意味着，算法一定会在某个时刻让 $R$ 到达 $end$ 这个位置。
• 在该时刻，算法维护的左指针为 $L_{algo}$。
• 此时算法计算出的长度是 $end - L_{algo} + 1$。

3. 反证假设

假设算法“略过”了最优解。 这意味着，当 $R$ 到达 $end$ 时，算法计算出的长度比标准答案短。 即：

4. 推导矛盾

既然 $L_{algo} > start$，说明左指针在之前的某个时刻（当右指针位于 $k \le end$ 时），被迫发生了一次“跳跃”，跳过了 $start$。

为什么 $L$ 会跳跃？ 根据算法逻辑，只有当窗口内出现重复元素时，$L$ 才会向右跳。 这说明： 在区间 $[start, L_{algo}-1]$ 之间存在某个位置 $p$，且 $arr[p]$ 与当前右指针 $arr[k]$ 相同（$arr[p] == arr[k]$）。

注意位置关系：

这意味着什么？ 这意味着在区间 $[start, end]$ 内部，存在一对重复元素 $(arr[p], arr[k])$。

矛盾产生： 我们一开始定义 $[start, end]$ 是**“无重复区间”**。 但推导表明，如果算法的 $L$ 跑到了 $start$ 的右边，那么 $[start, end]$ 内部必然包含重复元素。 这与定义矛盾！

5. 结论

因此，假设不成立。 当 $R$ 到达 $end$ 时，算法的左指针 $L_{algo}$ 绝对不可能大于 $start$。 同时，由于算法的 $L$ 只有在遇到冲突时才移动（贪心策略，尽可能保持 $L$ 靠左），所以 $L_{algo}$ 也不会小于 $start$（否则会有重复元素未被剔除）。

所以，必然有 $L_{algo} = start$。 算法必然会在 $R=end$ 这一刻，准确地计算出长度 $Len_{opt}$。

通俗版总结（直觉理解）

1. 右指针的地毯式搜索：右指针 $R$ 会扫过数组的每一个位置，所以**任何一个可能的“终点”**都不会被漏掉。
2. 左指针的“被迫”移动：左指针 $L$ 是懒惰的。除非万不得已（也就是真的遇到了重复，不移不行了），否则它绝不向右动一步。
3. 合体：既然每一个“终点”都试过了，而对于每一个终点，左指针都尽可能地“撑”到了最左边的极限位置。那么，每一个终点对应的“最长”区间其实都被我们算了一遍。最大值自然就在其中。

证明:最优性归纳法

使用 最优性归纳法 (Optimality Induction) 来证明，本质上是证明：在每一步迭代中，算法所维护的那个区间，都是以当前元素结尾的“局部最优解”。

如果我们能证明对于每一个位置 $i$，算法都算出了“以 $i$ 结尾的最长无重复区间”，那么全局最大值一定是这些局部最大值中的一个。

1. 定义状态

• 设 $S$ 为输入数组。
• 设 $L_{alg}(i)$ 为当算法处理到第 $i$ 个元素时，左指针 $L$ 的值。
• 设 $L_{opt}(i)$ 为理论上以 $S[i]$ 结尾的最长无重复区间的起始下标。
  • 也就是说，$S[L_{opt}(i) \dots i]$ 是以 $i$ 结尾的最长合法区间。

证明目标： 对于任意 $0 \le i < n$，都有 $L_{alg}(i) = L_{opt}(i)$。

2. 归纳证明过程

基础情况 (Base Case)

当 $i=0$ 时：

• 算法初始化 $L=0$。由于之前没有任何元素，没有冲突，$L_{alg}(0) = 0$。
• 理论上，区间 $[0, 0]$ 只有一个元素，不可能重复，起始点 $L_{opt}(0) = 0$。
• 结论：$L_{alg}(0) = L_{opt}(0)$ 成立。

归纳步骤 (Inductive Step)

假设：对于 $i-1$，算法已经正确找到了最优左边界，即 $L_{alg}(i-1) = L_{opt}(i-1)$。 求证：在处理 $i$ 时，算法也能正确找到 $L_{alg}(i) = L_{opt}(i)$。

考虑当前元素 $S[i]$，设它上一次出现的下标为 $last\_pos$（如果没出现过，设为 -1）。

我们需要分两种情况讨论：

情况 A：$S[i]$ 在当前窗口内没有重复 即 $last\_pos < L_{alg}(i-1)$。

• 理论推导 ($L_{opt}$)： 既然 $S[i]$ 不在之前的区间 $S[L_{opt}(i-1) \dots i-1]$ 中出现，那么加上 $S[i]$ 后，整个区间依然是无重复的。为了让区间最长，左边界应该保持不变。 $\therefore L_{opt}(i) = L_{opt}(i-1)$。
• 算法行为 ($L_{alg}$)： 算法检查 map，发现 $last\_pos$ 小于当前 $L$，不触发更新（或 max 取值取了原来的 $L$）。 $\therefore L_{alg}(i) = L_{alg}(i-1)$。
• 匹配结果：两者相等。

情况 B：$S[i]$ 在当前窗口内发生了冲突 即 $last\_pos \ge L_{alg}(i-1)$。

• 理论推导 ($L_{opt}$)： 区间 $S[L_{opt}(i-1) \dots i-1]$ 是合法的，但加上 $S[i]$ 后，与位置 $last\_pos$ 的元素重复了。 为了消除重复并保持以 $i$ 结尾：
  1. 新的左边界必须在 $last\_pos$ 的右边（否则包含两个 $S[i]$）。
  2. 新的左边界不能比 $last\_pos + 1$ 更靠右（因为我们要找最长区间，且 $S[last\_pos+1 \dots i-1]$ 内部本身就是无重复的，加上 $S[i]$ 后也没问题）。 $\therefore$ 理论上的最优左边界必须跳到冲突点的下一位：$L_{opt}(i) = last\_pos + 1$。
• 算法行为 ($L_{alg}$)： 算法检测到 $last\_pos \ge L$，执行 L = last_pos + 1。 $\therefore L_{alg}(i) = last\_pos + 1$。
• 匹配结果：两者相等。

3. 结论

1. 通过归纳法证明了：算法维护的 $L$ 指针，始终是“以当前右指针结尾的最长无重复子串”的理论最优左边界。
2. 既然算法正确计算了每一个位置 $i$ 对应的最长区间长度 $Len(i)$。
3. 那么，算法过程中记录的 max_len = max(Len(0), Len(1)... Len(n-1))，必然就是全局的最优解。

证毕。