题目描述

难度分:$1500$

输入$n(1 \leq n \leq 2000)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

删除$a$的一个连续子数组（可以是空的），使得剩余元素互不相同。

输出这个子数组的最短长度。

输入样例$1$

3
1 2 3

输出样例$1$

0

输入样例$2$

4
1 1 2 2

输出样例$2$

2

输入样例$3$

5
1 4 1 4 9

输出样例$3$

2

算法

二分答案

比较容易看出单调性，肯定是删的子数组长度越大，越容易让剩余数字各不相同，因此二分这个最短长度。

对于一个给定的删除长度$len$，它对应的子数组为$[l,r]$，那么在$check$的时候我们就需要知道$[1,l)$和$(r,n]$中的元素是不是互不相同。可以做一个前后缀分解，维护两个哈希表$pre$、$suf$，$pre$存前缀$[1,l)$的元素频数，$suf$存后缀$(r,n]$的元素频数。

1. 如果对于一个长度$len$，存在一个子数组$[l,r]$满足$pre$的大小为$l$，$suf$的大小为$n-r$，且这两个哈希表的$key$没有交集，就说明可以通过删除$[l,r]$使得剩余的元素互不相同，返回true。记录答案，并往左搜索看长度能不能更小。
2. 否则$len$就太小了，应该往右搜索。

复杂度分析

时间复杂度

二分长度的时间复杂度为$O(log_2n)$。$check$的时候滑动窗口的时间复杂度是$O(n)$的，在这个过程中维护$pre$和$suf$两个哈希表。检查$pre$和$suf$交集是否为空的时间复杂度也是$O(n)$，因为在最差情况下$pre$和$suf$中的键值对数量为$O(n)$级别。

综上，整个算法的时间复杂度为$O(n^2log_2n)$。

空间复杂度

空间消耗主要在于$pre$和$suf$两个哈希表，在最差情况下一共会存$O(n)$个键值对，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 2001;
int n, a[N];

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

bool check(int len) {
    unordered_map<int, int, custom_hash> pre, suf;
    for(int i = len + 1; i <= n; i++) {
        suf[a[i]]++;
    }
    if(suf.size() == n - len) return true;
    for(int r = len + 1; r <= n; r++) {
        suf[a[r]]--;
        if(suf[a[r]] == 0) suf.erase(a[r]);
        int l = r - len;
        pre[a[l]]++;
        bool ok = pre.size() == l && suf.size() == n - r;
        for(auto&[num, cnt]: pre) {
            if(!ok) break;
            if(suf.count(num)) {
                ok = false;
            }
        }
        if(ok) return ok;
    }
    return false;
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    int l = 0, r = n - 1;
    while(l < r) {
        int mid = l + r >> 1;
        if(check(mid)) {
            r = mid;
        }else {
            l = mid + 1;
        }
    }
    printf("%d\n", r);
    return 0;
}