核心思路
1. 二分答案：若长度 len 存在唯一子数组，则 len+1 也必然存在（子数组越长越不容易重复），满足单调性。
2. 双模数前缀哈希：用两组不同的 base/mod 计算子数组哈希，拼成 (u64, u64) 元组作为唯一标识，O(1) 比较子数组。
3. 统计频次：对每个候选长度，统计所有子数组哈希出现次数，若存在仅出现 1 次的即为可行。
Rust 实现
use std::collections::HashMap;
impl Solution {
const MOD1: u64 = 1_000_000_007;
const MOD2: u64 = 998_244_353;
const BASE1: u64 = 131;
const BASE2: u64 = 13331;
pub fn smallest_unique_subarray(nums: Vec<i32>) -> i32 {
let n = nums.len();
if n == 1 {
return 1;
}
// 预处理前缀哈希与幂次
let mut pre1 = vec![0u64; n + 1];
let mut pre2 = vec![0u64; n + 1];
let mut pw1 = vec![1u64; n + 1];
let mut pw2 = vec![1u64; n + 1];
for i in 0..n {
// nums[i] 可能为负数，需要加 mod 保证非负
let v = (nums[i] % Self::MOD1 as i32 + Self::MOD1 as i32) as u64;
pre1[i + 1] = (pre1[i] * Self::BASE1 + v) % Self::MOD1;
let v2 = (nums[i] % Self::MOD2 as i32 + Self::MOD2 as i32) as u64;
pre2[i + 1] = (pre2[i] * Self::BASE2 + v2) % Self::MOD2;
pw1[i + 1] = pw1[i] * Self::BASE1 % Self::MOD1;
pw2[i + 1] = pw2[i] * Self::BASE2 % Self::MOD2;
}
// 获取区间 [i, i+len) 的哈希值
let get_hash = |pre: &[u64], pw: &[u64], i: usize, len: usize, modulus: u64| -> u64 {
let h = (pre[i + len] + modulus - pre[i] * pw[len] % modulus) % modulus;
h
};
// 检查是否存在唯一的子数组
let has_unique = |length: usize| -> bool {
let mut cnt: HashMap<(u64, u64), i32> = HashMap::new();
for i in 0..=(n - length) {
let h1 = get_hash(&pre1, &pw1, i, length, Self::MOD1);
let h2 = get_hash(&pre2, &pw2, i, length, Self::MOD2);
*cnt.entry((h1, h2)).or_insert(0) += 1;
}
cnt.values().any(|&v| v == 1)
};
// 二分最小长度
let (mut lo, mut hi, mut ans) = (1usize, n, n);
while lo <= hi {
let mid = (lo + hi) / 2;
if has_unique(mid) {
ans = mid;
if mid == 0 { break; }
hi = mid - 1;
} else {
lo = mid + 1;
}
}
ans as i32
}
}
关键点解析
- 前缀哈希公式：hash[i..i+len) = (pre[i+len] - pre[i] × base^len + MOD) % MOD，O(1) 计算任意子数组哈希。加 MOD 是为了防止减法产生负数。
- 负数处理：nums[i] 可能为负数，计算哈希前先 (nums[i] % MOD + MOD) % MOD 保证非负。
- 双哈希元组：Rust 原生支持 (u64, u64) 作为 HashMap 的 key（实现了 Hash + Eq），无需手动拼接。
- 二分单调性：长度越大，子数组越独特，"存在唯一子数组"这一性质单调递增。
- 时间复杂度：O(n log n)，二分 O(log n) 轮，每轮 O(n) 遍历 + HashMap 操作。
- 空间复杂度：O(n)，存储前缀哈希、幂次数组和 HashMap。
示例验证
nums = [1,1,2,2,1]：
- 长度 1：1 出现 3 次，2 出现 2 次 → 无唯一
- 长度 2：[1,1]、[1,2]、[2,2]、[2,1] 各出现 1 次 → 有唯一 ✅
- 二分得答案 2
需要我把这道题的 TypeScript 版本也补上吗？
