完美排序题解

完美排序题目链接

题目简述

给定一个长度为的正整数数组，你需要从中找到一个连续的子数组，使得这个子数组是一个“完美排列”。

什么是“完美排列”？
如果一个子数组的长度为，且它恰好包含了数字（每个数字出现且仅出现一次），那么它就是完美排列。

目标：
找到所有满足条件的子数组中，长度最长的那个，输出其长度。

数据范围：。

解题思路

数据范围提示我们可以使用的算法。我们可以暴力枚举所有的子数组，并快速判断它们是否合法。

本题主要有两种解题思路：第一种是双指针维护窗口，第二种是异或哈希。

其中，异或哈希方法在进行的预处理后，可以地快速求出某个区间是否为完美排列；若掌握该方法，本题的难度将简化为纯粹的暴力枚举。

注：本文接下来的题解仅针对第一种“双指针维护窗口”的解法进行讲解，关于异或哈希，可以自行查阅资料进行扩展学习。

核心判定逻辑

一个长度为的子数组要是“完美排列”，必须同时满足两个条件：

无重复：子数组里没有重复的数字。
数值连续：子数组里的数字必须是。

快速判断技巧：
在保证没有重复数字的前提下，如果子数组中的最大值等于子数组的长度，那么这个子数组一定是由组成的。

算法流程（配合 Std 代码）

我们使用双重循环来枚举所有可能的子数组：

枚举区间：
- 外层循环：枚举子数组的起点（从 1 到）。
- 内层循环：枚举子数组的终点（从到）。
状态维护：
- 在每次确定一个新的起点时，我们需要清空计数器（cnt 数组），并重置当前最大值 maxx。
- 随着向后移动，我们逐步将加入考量。
合法性检查：
- 查重：检查之前是否出现过。
  - 若重复：说明从开始、经过及以后的子数组都不可能合法了，直接 break 退出当前内层循环（剪枝）。
  - 若不重复：
    - 标记已出现。
    - 更新当前区间的最大值 maxx = max(maxx, a[j])。
    - 判断：如果 maxx == (j - i + 1)（最大值等于当前长度），说明找到了一个完美排列，更新最终答案 ans。

AC 代码 (C++)

双指针维护窗口解法

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
	int n;
	cin >> n; // 输入数组长度
	
	// a 存储原数组，cnt 用于标记数字是否出现过
	// 开大一点 (+10) 防止越界
	vector<int> a(n + 10), cnt(n + 10);
	
	int ans = 0;  // 最小的完美排列长度是0（即没有），初始化为0
	int maxx = 0; // 用于记录当前枚举区间的最大值
	
	// 读入数组，下标从 1 开始方便计算长度
	for (int i = 1; i <= n; i++) cin >> a[i];
	
	// 外层循环：枚举子数组的起点 i
	for (int i = 1; i <= n; i++) {
		// 内层循环：枚举子数组的终点 j
		for (int j = i; j <= n; j++) {
			
			// 初始化阶段：
			// 当 j == i 时，说明刚开始一个新的起点枚举
			// 此时必须把辅助数组 cnt 清空，并重置 maxx
			if (j == i) {
				// 注意：这里的时间复杂度是 O(N)，总复杂度是 O(N^2)，因为j == i只有n种情况
				for (int k = 1; k <= n; k++) cnt[k] = 0;
				maxx = 0;
			}
			
			// 核心逻辑：检查重复
			if (cnt[a[j]] == 0) {
				// 没出现过，标记为已出现
				cnt[a[j]] = 1;
				
				// 更新当前区间的最大值
				maxx = max(maxx, a[j]);
				
				// 完美排列判定：
				// 1. 无重复（已通过 if 保证）
				// 2. 最大值 == 长度
				if (maxx == j - i + 1) {
					ans = max(ans, j - i + 1); // 更新最大长度
				}
			} else {
				// 出现过重复数字！
				// 剪枝：一旦出现重复，后续更长的子数组必然也重复，直接停止当前起点的枚举
				break; 
			}
		}
	}
	cout << ans << endl;
}

signed main() {
	// 加速输入输出，防止 I/O 耗时过大
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	
	int t = 1;
	// cin >> t; // 本题只有一组数据，若有多组数据请取消注释
	while (t--) solve();
	
	return 0;
}

异或哈希解法

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;

// 初始化 64 位随机数生成器，使用当前时间作为种子，保证每次运行的哈希值不同，防止被针对
mt19937_64 rd(time(0));

void solve() {
    int n, ans = 1;
    cin >> n;
    
    // a: 存储输入数组
    // pre: 输入数组的异或哈希前缀和
    // rd2: 随机映射表，rd2[x] 表示数字 x 对应的随机校验码
    // pre2: 标准“完美排列” (1, 2, ..., i) 的异或哈希前缀和
    vector<int> a(n + 10), pre(n + 10), rd2(n + 10, -1), pre2(n + 10);
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        // 给数字 i 分配一个随机的 64 位整数作为“指纹”
        // 这一步是为了防止普通的异或（如 1^4 == 2^3）产生的哈希冲突
        rd2[i] = rd();
    }
    
    for (int i = 1; i <= n; i++) {
        // 计算原数组的前缀哈希：
        // 这里的哈希规则是：数字 x 的哈希值 = x ^ rd2[x]
        // 异或性质：a ^ b ^ a = b，利用前缀异或可以快速求出任意区间的异或和
        // pre[i] 表示 a[1]...a[i] 的哈希总和
        pre[i] = pre[i - 1] ^ a[i] ^ rd2[a[i]];
        
        // 计算标准完美排列的前缀哈希：
        // pre2[i] 表示集合 {1, 2, ..., i} 的哈希总和
        // 即：(1^rd2[1]) ^ (2^rd2[2]) ^ ... ^ (i^rd2[i])
        pre2[i] = pre2[i - 1] ^ i ^ rd2[i];
    }
    
    // 双重循环枚举所有可能的子数组
    // i 是起始位置，j 是结束位置
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            // 区间 [i, j] 的长度
            int len = j - i + 1;
            
            // 核心判断逻辑：
            // 1. (pre[j] ^ pre[i - 1]) 算出了原数组区间 a[i...j] 的哈希值总和
            // 2. pre2[len] 是标准答案 {1, 2, ..., len} 的哈希值总和
            // 如果两者相等，说明区间 a[i...j] 里的元素集合与 {1...len} 完全一致
            // 仅仅是顺序不同（异或满足交换律，顺序不影响结果），即满足“完美排列”
            if ((pre[j] ^ pre[i - 1]) == pre2[j - i + 1])
                ans = max(ans, j - i + 1);
        }
    }
    cout << ans << endl;
}

signed main() {
    int t = 1;
    // 优化 I/O 速度
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    // cin>>t;    
    while (t--) solve();
    return 0;
}

‍

完美排序#题解