🤖 AI总结
主题
求解数组中最短唯一连续子数组的长度。
摘要
通过后缀数组和LCP数组，计算每个后缀的最短唯一前缀长度，取最小值作为答案，算法高效且可处理大规模数据。
关键信息
- 1 利用后缀数组与LCP数组判断子数组唯一性
- 2 将整数数组转换为字节序列以使用Go标准库
- 3 算法复杂度为O(n log n)时间，O(n)空间
2026-08-27：最短唯一子数组。用go语言，给定一个整数数组，我们需要找到所有可能的连续非空片段中，那些在数组里只出现一次的片段。所谓“出现一次”，是指不存在另一个片段，长度相同且每个对应位置的数字都完全一样。我们的目标是找出所有这样的独特片段里，长度最短的那个，并返回这个最小长度值。
1 <= nums.length <= 100000。
1 <= nums[i] <= 100000。
输入： nums = [3,3,3]。
输出： 3。
解释：
长度为 1 的子数组：[3] → 出现 3 次
长度为 2 的子数组：[3, 3] → 出现 2 次
长度为 3 的子数组：[3, 3, 3] → 出现 1 次
子数组 [3, 3, 3] 是唯一的，因此最小唯一子数组的长度为 3。
题目来自力扣3934。
算法分步骤描述（基于后缀数组 + LCP） 问题核心
给定整数数组nums，需要找出所有仅出现一次的连续子数组（即不存在另一个完全相同的子数组），并返回其中最短长度。
等价于：对每个后缀nums[i:]，其所有前缀中，若某个前缀在其他后缀中不再出现，则它是一个唯一子数组；我们要找所有后缀中符合条件的最短前缀长度。
步骤 1：将整数数组转化为字节序列（用于后缀数组构造）
• 题目中nums[i] <= 1e5，每个整数可以用 3 个字节完整表示（位移操作）。
• 将每个整数拆成 3 个字节（高位到低位），拼接成一个大的字节数组tmp。
• 这样做的目的是借用 Go 标准库suffixarray直接处理字节切片，避免手动实现整数后缀数组。
（注：由于每个整数固定 3 字节，整数数组的后缀与字节序列中偏移为 3 的倍数的后缀一一对应。）
步骤 2：构造后缀数组并转换为整数下标
• 调用suffixarray.New(tmp)得到后缀数组（内部为sa，类型[]int32），它记录了字节序列中所有后缀的字典序排名。
• 由于整数后缀只对应偏移为3 的倍数的起始位置，我们遍历sa，只保留p % 3 == 0的位置，并将坐标除以 3 得到原整数数组的下标。
• 最终得到整数数组nums的后缀数组sa（长度 n），sa[i]表示字典序第 i 小的后缀在原数组中的起始索引（0-based）。
步骤 3：建立排名数组rank
•rank[p]表示后缀nums[p:]在字典序中的排名（即sa[rank[p]] == p）。
• 遍历sa，对每个索引 i，令rank[ sa[i] ] = i。
步骤 4：计算高度数组height（LCP 数组）
•height[0] = 0（哨兵）。
• 对于 i > 0，height[i]= 后缀nums[ sa[i] : ]与nums[ sa[i-1] : ]的最长公共前缀长度。
• 利用Kasai 算法线性计算：
• 从 i = 0 到 n-1，令 h = 当前已经匹配的长度（初始 0）。
• 若rank[i] > 0，则与排名前一位的后缀比较，不断扩展公共前缀长度 h（同时保证不越界）。
• 记录height[ rank[i] ] = h，然后若 h>0，则 h–（因为下一次 i+1 时，前缀长度至少为 h-1）。
步骤 5：求每个后缀可形成的最短唯一子数组长度
• 对于后缀nums[ sa[i] : ]，它与左右相邻后缀（即排名 i-1 和 i+1）的 LCP 最大值maxLCP决定了：
任何长度 ≤maxLCP的前缀都会在相邻后缀中出现，因此不唯一；
长度 ≥maxLCP + 1的前缀才可能唯一。
• 因此，该后缀能贡献的最短唯一子数组长度为：
• 如果 i 不是最后一个（即 i < n-1），则考虑左右两边：uniqueLen = max(height[i], height[i+1]) + 1。
• 如果 i 是最后一个（i == n-1），则只有左边：uniqueLen = height[i] + 1。
• 同时，uniqueLen不能超过该后缀自身的长度（即n - sa[i]），否则子数组超出数组范围，不合理。
• 取所有合法uniqueLen的最小值，即为答案。
步骤 6：返回结果
• 初始ans = n（最大可能长度）。
• 遍历所有后缀，更新ans = min(ans, uniqueLen)。
• 最终返回ans。
示例推演（nums = [3,3,3]）
• 后缀数组：所有后缀为[3,3,3],[3,3],[3]，字典序相同（因为元素全等），排序后可能为[0,1,2]或[2,1,0]，但实际顺序任意（只要排名稳定）。
• rank 数组：每个后缀排名相邻。
• height 数组：任意相邻后缀的 LCP 分别为 2 和 1（取决于排序），但最大值计算后可得：
• 对后缀[3,3,3]，与左右 LCP 最大值 = 2，则 uniqueLen = 3，合法。
• 其他后缀的 uniqueLen 也会是 3（因为长度限制），最终 ans = 3。
时间与空间复杂度
•时间复杂度：
• 构造后缀数组：suffixarray.New内部实现基于DC3 算法（线性），但理论上通常视为O(n)，不过标准库可能采用快速排序（O(n log n)）。严格来说，对于长度 n ≤ 1e5，可认为是O(n log n)。
• 构建 rank 和 height：均 O(n)。
• 遍历求答案：O(n)。
• 总体O(n log n)，且常数较小。
•额外空间复杂度：
• 字节数组 tmp：O(n)。
• 后缀数组 sa：O(n)。
• rank 和 height 数组：O(n)。
• 其他辅助变量 O(1)。
• 总共O(n)。
总结
该算法利用后缀数组 + LCP 快速判断前缀重复性，将“唯一子数组”问题转化为每个后缀的最短唯一前缀问题，从而在线性扫描中得到答案。空间开销为 O(n)，时间开销为 O(n log n)，能够处理 n = 1e5 的数据规模。
Go完整代码如下：
package main
import (
"fmt"
"index/suffixarray"
"unsafe"
)
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func smallestUniqueSubarray(nums []int) int {
n := len(nums)
// 将每个整数拆成 3 个字节，用于构造后缀数组
tmp := make([]byte, 0, n*3)
for _, x := range nums {
tmp = append(tmp, byte(x>>16), byte(x>>8), byte(x))
}
// 利用 unsafe 获取 suffixarray 内部的 sa 切片
type _tp struct {
_ []byte
sa []int32
}
_sa := (*_tp)(unsafe.Pointer(suffixarray.New(tmp))).sa
// 只保留偏移为 3 的倍数的位置，对应原数组的整数后缀
sa := make([]int32, 0, n)
for _, p := range _sa {
if p%3 == 0 {
sa = append(sa, p/3)
}
}
// 后缀名次数组 rank
rank := make([]int, n)
for i, p := range sa {
rank[p] = i
}
// 高度数组 height（LCP 数组）
height := make([]int, n)
h := 0
for i, rk := range rank {
if h > 0 {
h--
}
if rk > 0 {
for j := int(sa[rk-1]); i+h < n && j+h < n && nums[i+h] == nums[j+h]; h++ {
}
}
height[rk] = h
}
ans := n
for i, h := range height {
// 该后缀与左右相邻后缀的 LCP 最大值 +1 即为最小唯一前缀长度
uniqueLength := h + 1
if i < n-1 {
uniqueLength = max(h, height[i+1]) + 1
}
if uniqueLength <= n-int(sa[i]) {
ans = min(ans, uniqueLength)
}
}
return ans
}func main() {
nums := []int{3, 3, 3}
result := smallestUniqueSubarray(nums)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-def build_suffix_array(nums):
"""构建整数数组的后缀数组（倍增算法）"""
n = len(nums)
if n == 1:
return [0]
# 初始排名：直接用数值（但需注意数值可能较大，排序时依然正确）
rank = list(nums)
sa = list(range(n))
k = 1
tmp = [0] * n
while True:
# 按 (rank[i], rank[i+k] if i+k else -1 ) 排序
sa.sort(key=lambda i: (rank[i], rank[i + k] if i + k < n else -1 ))
tmp[sa[ 0 ]] = 0
for i in range ( 1 , n):
prev, cur = sa[i - 1 ], sa[i]
prev_key = (rank[prev], rank[prev + k] if prev + k < n else -1 )
cur_key = (rank[cur], rank[cur + k] if cur + k < n else -1 )
tmp[cur] = tmp[prev] + ( 1 if cur_key != prev_key else 0 )
rank, tmp = tmp, rank # 交换，tmp 变为旧 rank（后续会被覆盖）
if rank[sa[ -1 ]] == n - 1 : # 所有排名都不同
break
k <<= 1
return sa
def build_lcp(nums, sa):
"" "计算 LCP 数组（height），height[i] = LCP(sa[i], sa[i-1])，height[0]=0" ""
n = len (nums)
rank = [ 0 ] * n
for i, p in enumerate(sa):
rank[p] = i
height = [ 0 ] * n
h = 0
for i in range (n):
if rank[i] > 0 :
j = sa[rank[i] - 1 ]
while i + h < n and j + h < n and nums[i + h] == nums[j + h]:
h += 1
height[rank[i]] = h
if h > 0 :
h -= 1
return height
def smallest_unique_subarray(nums):
n = len (nums)
if n == 0 :
return 0
sa = build_suffix_array(nums)
height = build_lcp(nums, sa)
ans = n
for i in range (n):
# 当前后缀与左右相邻后缀的 LCP 最大值 + 1 即为最小唯一前缀长度
unique_len = height[i] + 1
if i < n - 1 :
unique_len = max(height[i], height[i + 1 ]) + 1
# 不能超过后缀自身的长度
if unique_len <= n - sa[i]:
ans = min(ans, unique_len)
return ans
if __name__ == "__main__" :
nums = [ 3 , 3 , 3 ]
result = smallest_unique_subarray(nums)
print (result)
C++完整代码如下：
using namespace std;
// 构建后缀数组 sa，sa[i] 表示第 i 小的后缀的起始下标
vector buildSuffixArray(const vector& nums) {
int n = nums.size();
vector sa(n), rank(n), tmp(n);
// 初始排名：按第一个元素
for (int i = 0; i < n; i++) {
sa[i] = i;
rank[i] = nums[i];
}
// 倍增排序
for (int k = 1; k < n; k <<= 1) {
auto cmp = [&](int i, int j) {
if (rank[i] != rank[j]) return rank[i] < rank[j];
int ri = (i + k < n) ? rank[i + k] : -1;
int rj = (j + k < n) ? rank[j + k] : -1;
return ri < rj;
};
sort(sa.begin(), sa.end(), cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++) {
tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
}
rank = tmp;
if (rank[sa[n - 1]] == n - 1) break; // 全部排名不同，提前结束
}
return sa;
}
// 计算 height 数组，height[i] = LCP(sa[i], sa[i-1])，height[0] = 0
vector buildHeight(const vector& nums, const vector& sa) {
int n = nums.size();
vector rank(n);
for (int i = 0; i < n; i++) rank[sa[i]] = i;
vector height(n, 0);
int h = 0;
for (int i = 0; i < n; i++) {
if (rank[i] > 0) {
int j = sa[rank[i] - 1];
while (i + h < n && j + h < n && nums[i + h] == nums[j + h]) h++;
height[rank[i]] = h;
if (h > 0) h--;
}
}
return height;
}
int smallestUniqueSubarray(const vector& nums) {
int n = nums.size();
if (n == 0) return 0; // 根据题意不会出现
vector sa = buildSuffixArray(nums);
vector height = buildHeight(nums, sa);
int ans = n;
for (int i = 0; i < n; i++) {
// 当前后缀与左右相邻后缀的 LCP 最大值 +1 即为最小唯一前缀长度
int uniqueLen = height[i] + 1;
if (i < n - 1) {
uniqueLen = max(height[i], height[i + 1]) + 1;
}
// 不能超过后缀自身长度
if (uniqueLen <= n - sa[i]) {
ans = min(ans, uniqueLen);
}
}
return ans;
}int main() {
vector nums = {3, 3, 3};
int result = smallestUniqueSubarray(nums);
cout << result << endl;
return 0;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
