题解：P12280 [蓝桥杯 2024 国 Python A] 特别的数组

思路与算法

主思路与算法

首先，题目要求的是移除一个区间后剩下的元素必须全部唯一。那么最大的剩余长度就是原长度减去被移除区间的长度。所以，问题转化为找到最小的需要移除的区间长度，这样剩下的部分就最长。因此，我们的目标应该是找到这样的一个最小的区间，当移除它之后，剩下的元素都是唯一的。

那怎么找到这个最小的区间呢？直接想到的是，如果我们能确定哪些元素是重复的，那么我们需要移除的区间必须覆盖所有重复元素中的一个或多个，使得剩下的元素不再重复。但这似乎比较复杂，因为可能有多个重复元素分布在数组的不同位置。

所以，我们思考，如何高效地找到这个最小的移除区间呢？直接暴力枚举所有可能的L和R显然不可行，因为时间复杂度会是 \(O(n^2)\)，对于 \(n = 1 \times 10^5\) 的情况，这完全无法处理。

这时候，想到滑动窗口（双指针）的方法。滑动窗口通常用来处理子数组或子区间的问题，尤其是涉及连续元素的情况。那么，这里的问题是否可以转化为滑动窗口的问题？

滑动窗口的核心思想是维护一个窗口，使得窗口内的元素满足某种条件，而窗口外的元素满足另一种条件。例如，在这个问题中，我们的目标是找到一个窗口 \([L, R]\)，当移除这个窗口后，剩下的元素都是唯一的。也就是说，窗口外的元素必须全部唯一。

换句话说，我们需要找到一个窗口，使得在数组的左右两部分（窗口左边和窗口右边）中的元素都没有重复。或者更准确地说，整个数组除了窗口内的元素之外，剩下的元素都是唯一的。

这时候，问题转化为寻找一个窗口，使得窗口外的元素都不重复。找到这样的窗口后，我们要找出其中长度最小的那个窗口，这样原数组长度减去这个窗口长度就是最大的剩余长度。

于是，滑动窗口的思路是可行的。具体来说，我们需要从数组中移除一个连续区间 \([L, R]\)，使得剩余元素全为唯一，且剩余部分尽可能长。目标转化为寻找移除的最小区间长度，使得剩余元素唯一。

这个思路的关键点在于，如何高效地维护窗口外元素的出现次数，并快速判断是否满足条件。使用滑动窗口可以在 \(O(n)\) 的时间复杂度内完成，因为每个元素最多被左右指针各遍历一次（计算过程中）。

副算法

哈希表模拟：通过数组 \(cnt\) 直接索引元素值，统计频率，避免复杂数据结构。

代码

首先统计整个数组中每个元素的出现次数。如果原数组已经是所有元素唯一的（特殊情况），那么不需要移除任何区间，直接返回 \(n\)。否则，我们需要找到最小的窗口 \([L, R]\)，使得移除这个窗口后剩下的元素唯一。

接着，使用滑动窗口的方法，维护左右指针，以及窗口外的元素的频率表。我们这里命名一个变量 \(over-cnt\)，表示窗口外有多少个元素的出现次数超过 \(1\)。右指针不断右移，将当前元素移出窗口外（即其频率减 \(1\)）。如果这个操作导致该元素的频率从 \(2\) 变为 \(1\) ，那么 \(over_cnt\) 减 \(1\)，因为该元素在窗口外不再重复。

当 \(over-cnt\) 变为 \(0\) 时，说明窗口外的元素没有重复。此时，尝试收缩左指针，移动左指针，将元素重新加入窗口外（即其频率加 \(1\)）。如果某个元素的频率从 \(1\) 变为 \(2\)，则 \(over-cnt\) 加 \(1\)，此时停止收缩，记录当前窗口的长度是否为最小值。

最终，找到最小的窗口长度，原数组长度减去这个长度就是答案。

我们需要从数组中移除一个连续区间 \([L, R]\)，使得剩余元素全为唯一，且剩余部分尽可能长。目标转化为寻找移除的最小区间长度，使得剩余元素唯一。

最后献上我的几篇代码：

C++C#JavaPython

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int a[MAXN];
int cnt[MAXN * 2];
int main() {
    int n;
    cin >> n;
    // 统计全局频率
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    // 计算初始重复元素种类数
    int over_cnt = 0;
    for (int i = 0; i < MAXN * 2; ++i) {
        if (cnt[i] > 1) over_cnt++;
    }
    // 若数组本身无重复，直接返回
    if (over_cnt == 0) {
        cout << n;
        return 0;
    }
    int min_win = n;
    int left = 0;
    for (int right = 0; right < n; ++right) {
        int x = a[right];
        cnt[x]--; // 移出窗口外（保留该元素）
        if (cnt[x] == 1)
            over_cnt--;
        // 当窗口外无重复时，尝试收缩左边界
        while (over_cnt == 0 && left <= right) {
            min_win = min(min_win, right - left + 1);
            int y = a[left];
            cnt[y]++; // 将元素移回窗口外（移除该元素）
            if (cnt[y] == 2)
                over_cnt++;
            left++;
        }
    }
    cout << n - min_win;
    return 0;
}

using System;

public class Program
{
    public static void Main()
    {
        const int MAXN = 100005 * 2;
        int n = int.Parse(Console.ReadLine());
        string[] input = Console.ReadLine().Split(' ');
        int[] a = Array.ConvertAll(input, int.Parse);
        int[] cnt = new int[MAXN];
        // 统计所有元素频率
        foreach (int x in a)
        {
            cnt[x]++;
        }
        // 计算初始重复元素种类数
        int over_cnt = 0;
        for (int i = 0; i < MAXN; i++)
        {
            if (cnt[i] > 1) over_cnt++;
        }
        // 若数组本身无重复，直接返回
        if (over_cnt == 0)
        {
            Console.WriteLine(n);
            return;
        }
        int min_win = n;
        int left = 0;
        for (int right = 0; right < n; right++)
        {
            int x = a[right];
            cnt[x]--; // 移出窗口外（保留该元素）
            if (cnt[x] == 1) over_cnt--;
            // 当窗口外无重复时，尝试收缩左边界
            while (over_cnt == 0 && left <= right)
            {
                min_win = Math.Min(min_win, right - left + 1);
                int y = a[left];
                cnt[y]++; // 将元素移回窗口外（移除该元素）
                if (cnt[y] == 2) over_cnt++;
                left++;
            }
        }
        Console.WriteLine(n - min_win);
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        final int MAXN = 100005 * 2;
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        String[] input = scanner.nextLine().split(" ");
        int[] a = Arrays.stream(input).mapToInt(Integer::parseInt).toArray();
        int[] cnt = new int[MAXN];
        // 统计所有元素频率
        for (int x : a) {
            cnt[x]++;
        }
        // 计算初始重复元素种类数
        int overCnt = 0;
        for (int i = 0; i < MAXN; i++) {
            if (cnt[i] > 1) overCnt++;
        }
        // 若数组本身无重复，直接返回
        if (overCnt == 0) {
            System.out.println(n);
            return;
        }
        int minWin = n;
        int left = 0;
        for (int right = 0; right < n; right++) {
            int x = a[right];
            cnt[x]--; // 移出窗口外（保留该元素）
            if (cnt[x] == 1) overCnt--;
            // 当窗口外无重复时，尝试收缩左边界
            while (overCnt == 0 && left <= right) {
                minWin = Math.min(minWin, right - left + 1);
                int y = a[left];
                cnt[y]++; // 将元素移回窗口外（移除该元素）
                if (cnt[y] == 2) overCnt++;
                left++;
            }
        }
        System.out.println(n - minWin);
    }
}

n = int(input())
a = list(map(int, input().split()))
from collections import defaultdict
cnt = defaultdict(int)
for x in a:
    cnt[x] += 1
over_cnt = sum(1 for x in cnt if cnt[x] > 1)
if over_cnt == 0:
    print(n)
    exit()
min_win = n
left = 0
for right in range(n):
    x = a[right]
    cnt[x] -= 1
    if cnt[x] == 1:
        over_cnt -= 1
    while over_cnt == 0 and left <= right:
        current_win = right - left + 1
        if current_win < min_win:
            min_win = current_win
        y = a[left]
        cnt[y] += 1
        if cnt[y] == 2:
            over_cnt += 1
        left += 1
print(n - min_win)