解题思路

我们希望通过至多一次删除一个连续子段，使剩余序列所有元素互不相同（“多彩”）。

等价变形：删除子段 $[l, r-1]$ 后，剩下的是前缀 $a[0..l-1]$ 与后缀 $a[r..n-1]$。要想整体无重复，必须同时满足：

1. 前缀内部无重复；
2. 后缀内部无重复；
3. 前缀元素集合与后缀元素集合不相交。

基于此可以用双指针 + 哈希集合线性求解：

1. 先从右往左扩展一个最长无重复后缀。 用集合 Suf 自右向左加入元素，遇到第一个重复就停止；此时得到最小的起点 r，使得区间 [r, n-1] 无重复。

2. 然后从左往右枚举前缀终点 l，维护前缀集合 Pre（始终保证前缀无重复）。

   • 在每个 l 上，当前需要删除的长度是 r - l，用它更新答案。
   • 若要把 x = a[l] 加入前缀，为了保证“前后缀不相交”，就推动 r 向右，并从 Suf 中移除经过的元素，直到 x 不在 Suf 中为止。
   • 若 x 已在 Pre 中，则说明扩展这个前缀会产生内部重复，后续更大的前缀也必然重复，直接停止。

3. 在整个过程中，l 与 r 都只会单调向右移动一次，因此总复杂度为 $O(n)$。

这个做法本质是两端不相交的去重窗口：右端先准备一个无重复后缀，左端逐步扩展前缀，并用右指针“让路”以消除交集，从而枚举所有合法拆分，最小化删除段长度。

复杂度分析

• 时间复杂度：每个元素最多被左右指针访问/移出一次，$O(n)$；多组数据总计为 $O(\sum n)$（$\sum n \le 2\times10^5$）。
• 空间复杂度：两个集合存储当前前缀/后缀的元素，最坏 $O(n)$。

代码实现

Python

# 读入并输出均在主函数中；核心逻辑封装在函数中
import sys

def min_magic(a):
    n = len(a)
    # 1) 找到最小的 r 使得 [r..n-1] 为无重复后缀
    suf = set()
    i = n - 1
    while i >= 0 and a[i] not in suf:
        suf.add(a[i])
        i -= 1
    r = i + 1  # 初始无重复后缀的起点
    ans = r

    # 2) 枚举前缀终点 l，维护前缀集合与右指针 r
    pre = set()
    for l in range(n):
        # 当前删除长度
        ans = min(ans, r - l)

        x = a[l]
        # 若加入会在前缀内造成重复，后续更大前缀也不可能合法，停止
        if x in pre:
            break

        # 让右指针右移，直到后缀中不再包含 x，保持前后缀元素集合不相交
        while r < n and x in suf:
            suf.remove(a[r])
            r += 1

        pre.add(x)

    return ans

def main():
    data = list(map(int, sys.stdin.read().strip().split()))
    t = data[0]
    idx = 1
    out_lines = []
    for _ in range(t):
        n = data[idx]; idx += 1
        a = data[idx:idx+n]; idx += n
        out_lines.append(str(min_magic(a)))
    print("\n".join(out_lines))

if __name__ == "__main__":
    main()

Java

// 类名必须为 Main，ACM 风格从标准输入读写
import java.io.*;
import java.util.*;

/**
 * 思路：双指针 + 两个哈希集合
 * 1) 从右向左构造最短起点 r，使 [r..n-1] 无重复；
 * 2) 从左向右枚举前缀终点 l，维护前缀集合 pre；
 *    对于每个 l，答案候选为 r - l；
 *    若要把 a[l] 加入前缀，则右移 r 直到后缀集合不含 a[l]；
 *    若 a[l] 已在前缀中，则终止。
 */
public class Main {
    static int solveOne(int[] a) {
        int n = a.length;
        // 1) 初始化无重复后缀起点 r
        HashSet<Integer> suf = new HashSet<>();
        int i = n - 1;
        while (i >= 0 && !suf.contains(a[i])) {
            suf.add(a[i]);
            i--;
        }
        int r = i + 1;
        int ans = r;

        // 2) 枚举前缀终点 l
        HashSet<Integer> pre = new HashSet<>();
        for (int l = 0; l < n; l++) {
            ans = Math.min(ans, r - l);

            int x = a[l];
            // 前缀内部出现重复，无法再扩展，停止
            if (pre.contains(x)) break;

            // 右移 r 直到后缀不含 x
            while (r < n && suf.contains(x)) {
                suf.remove(a[r]);
                r++;
            }
            pre.add(x);
        }
        return ans;
    }

    // 简单高效输入
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); } while (c <= ' ');
            if (c == '-') { sgn = -1; c = read(); }
            while (c > ' ') {
                x = x * 10 + (c - '0');
                c = read();
            }
            return x * sgn;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        StringBuilder sb = new StringBuilder();
        int T = fs.nextInt();
        while (T-- > 0) {
            int n = fs.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = fs.nextInt();
            sb.append(solveOne(a)).append('\n');
        }
        System.out.print(sb.toString());
    }
}

C++

// ACM 风格：标准输入输出
#include <bits/stdc++.h>
using namespace std;

/*
思路：双指针 + 集合
1) 自右向左找到最小 r 使 [r..n-1] 无重复；
2) 自左向右枚举 l，维护前缀集合 pre；
   - 答案候选为 r - l；
   - 将 a[l] 加入前缀前，若和后缀有交集，则右移 r 并从后缀集合移除经过元素；
   - 若 a[l] 已在前缀中，无法继续（前缀会重复），停止。
*/
int solve_one(const vector<long long>& a) {
    int n = (int)a.size();

    // 1) 初始化无重复后缀起点 r
    unordered_set<long long> suf;
    suf.reserve(n * 2);
    int i = n - 1;
    while (i >= 0 && !suf.count(a[i])) {
        suf.insert(a[i]);
        --i;
    }
    int r = i + 1;
    int ans = r;

    // 2) 枚举前缀终点 l
    unordered_set<long long> pre;
    pre.reserve(n * 2);
    for (int l = 0; l < n; ++l) {
        ans = min(ans, r - l);

        long long x = a[l];
        // 前缀内出现重复，停止
        if (pre.count(x)) break;

        // 右移 r，直到后缀不含 x
        while (r < n && suf.count(x)) {
            suf.erase(a[r]);
            ++r;
        }
        pre.insert(x);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; 
    if (!(cin >> T)) return 0;
    while (T--) {
        int n; cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        cout << solve_one(a) << "\n";
    }
    return 0;
}

题目内容

小明喜欢多彩的数列。在他眼中，一个数列是多彩的，当且仅当数列中的元素互不相同。

具体的，数列 $b_1,b_2,…,b_n$ 。被认为是多彩的，当且仅当对于任意两个不同的下标 $ij(1≤i,j≤n,i≠j)$ ，都有 $b_i≠b_j$ 。

这天，小明拿到了一个长为 $n$ 的数列 {$a$} 。并且，他能选择施展他的魔法，选择一个非负整数 $k$ ，将这个数列中某一个长度为 $k$ 的连续子段删去(剩下的元素按原顺序拼接)，这个过程消耗 $k$ 个单位的魔力值。

因为施展魔法后小明会变得很虚弱，所以他只能施展该魔法至多一次。当然，如果 {$a$} 原来就是多彩的，他也可以不施展。

你能帮助小明计算，让数列 {$a$} 变得多彩所需的最小魔力值吗?

输入描述

单个测试用例点包含多组数据。

第一行一个正整数 $T$，表示数据组数。

对于接下来的每一组数据：

第一行一个正整数 $n$ 。

第二行 $n$ 个正整数以空格分隔，表示数列 {$a$} 。

$1≤Σn≤2*10^5,1≤a_i≤10^9$ 。

其中 $∑n$ 表示所有 $T$ 组数据的 $n$ 之和。

输出描述

对于每一组数据，输出一行一个整数，表示让 {$a$} 变得多彩所需的最小魔力值。

样例1

输入

3
10
8 7 1 2 7 6 3 4 6 5
5
10 20 30 40 50
7
1 2 1 3 4 5 6

输出

2
0
1

说明

对于第一组样例，删去区间 $[5,6]$ 能使数列变得多彩，消耗 $2$ 点魔力值。

可以证明没有更优的方案。

对于第二组样例，原数列已经多彩，故答案为 $0$ 。