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长度 nsa[i]表示字典序第 i 小的后缀在原数组中的起始索引0-based。步骤 3建立排名数组rankrank[p]表示后缀nums[p:]在字典序中的排名即sa[rank[p]] p。遍历sa对每个索引 i令rank[ sa[i] ] i。步骤 4计算高度数组heightLCP 数组height[0] 0哨兵。对于 i 0height[i] 后缀nums[ sa[i] : ]与nums[ sa[i-1] : ]的最长公共前缀长度。利用Kasai 算法线性计算从 i 0 到 n-1令 h 当前已经匹配的长度初始 0。若rank[i] 0则与排名前一位的后缀比较不断扩展公共前缀长度 h同时保证不越界。记录height[ rank[i] ] h然后若 h0则 h–因为下一次 i1 时前缀长度至少为 h-1。步骤 5求每个后缀可形成的最短唯一子数组长度对于后缀nums[ sa[i] : ]它与左右相邻后缀即排名 i-1 和 i1的 LCP 最大值maxLCP决定了任何长度 ≤maxLCP的前缀都会在相邻后缀中出现因此不唯一长度 ≥maxLCP 1的前缀才可能唯一。因此该后缀能贡献的最短唯一子数组长度为如果 i 不是最后一个即 i n-1则考虑左右两边uniqueLen max(height[i], height[i1]) 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)且常数较小。额外空间复杂度字节数组 tmpO(n)。后缀数组 saO(n)。rank 和 height 数组O(n)。其他辅助变量 O(1)。总共O(n)。总结该算法利用后缀数组 LCP 快速判断前缀重复性将“唯一子数组”问题转化为每个后缀的最短唯一前缀问题从而在线性扫描中得到答案。空间开销为 O(n)时间开销为 O(n log n)能够处理 n 1e5 的数据规模。Go完整代码如下packagemainimport(fmtindex/suffixarrayunsafe)funcmax(a,bint)int{ifab{returna}returnb}funcmin(a,bint)int{ifab{returna}returnb}funcsmallestUniqueSubarray(nums[]int)int{n:len(nums)// 将每个整数拆成 3 个字节用于构造后缀数组tmp:make([]byte,0,n*3)for_,x:rangenums{tmpappend(tmp,byte(x16),byte(x8),byte(x))}// 利用 unsafe 获取 suffixarray 内部的 sa 切片type_tpstruct{_[]bytesa[]int32}_sa:(*_tp)(unsafe.Pointer(suffixarray.New(tmp))).sa// 只保留偏移为 3 的倍数的位置对应原数组的整数后缀sa:make([]int32,0,n)for_,p:range_sa{ifp%30{saappend(sa,p/3)}}// 后缀名次数组 rankrank:make([]int,n)fori,p:rangesa{rank[p]i}// 高度数组 heightLCP 数组height:make([]int,n)h:0fori,rk:rangerank{ifh0{h--}ifrk0{forj:int(sa[rk-1]);ihnjhnnums[ih]nums[jh];h{}}height[rk]h}ans:nfori,h:rangeheight{// 该后缀与左右相邻后缀的 LCP 最大值 1 即为最小唯一前缀长度uniqueLength:h1ifin-1{uniqueLengthmax(h,height[i1])1}ifuniqueLengthn-int(sa[i]){ansmin(ans,uniqueLength)}}returnans}funcmain(){nums:[]int{3,3,3}result:smallestUniqueSubarray(nums)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defbuild_suffix_array(nums):构建整数数组的后缀数组倍增算法nlen(nums)ifn1:return[0]# 初始排名直接用数值但需注意数值可能较大排序时依然正确ranklist(nums)salist(range(n))k1tmp[0]*nwhileTrue:# 按 (rank[i], rank[ik] if ikn else -1) 排序sa.sort(keylambdai:(rank[i],rank[ik]ifiknelse-1))tmp[sa[0]]0foriinrange(1,n):prev,cursa[i-1],sa[i]prev_key(rank[prev],rank[prevk]ifprevknelse-1)cur_key(rank[cur],rank[curk]ifcurknelse-1)tmp[cur]tmp[prev](1ifcur_key!prev_keyelse0)rank,tmptmp,rank# 交换tmp 变为旧 rank后续会被覆盖ifrank[sa[-1]]n-1:# 所有排名都不同breakk1returnsadefbuild_lcp(nums,sa):计算 LCP 数组heightheight[i] LCP(sa[i], sa[i-1])height[0]0nlen(nums)rank[0]*nfori,pinenumerate(sa):rank[p]i height[0]*n h0foriinrange(n):ifrank[i]0:jsa[rank[i]-1]whileihnandjhnandnums[ih]nums[jh]:h1height[rank[i]]hifh0:h-1returnheightdefsmallest_unique_subarray(nums):nlen(nums)ifn0:return0sabuild_suffix_array(nums)heightbuild_lcp(nums,sa)ansnforiinrange(n):# 当前后缀与左右相邻后缀的 LCP 最大值 1 即为最小唯一前缀长度unique_lenheight[i]1ifin-1:unique_lenmax(height[i],height[i1])1# 不能超过后缀自身的长度ifunique_lenn-sa[i]:ansmin(ans,unique_len)returnansif__name____main__:nums[3,3,3]resultsmallest_unique_subarray(nums)print(result)C完整代码如下#includeiostream#includevector#includealgorithm#includestringusingnamespacestd;// 构建后缀数组 sasa[i] 表示第 i 小的后缀的起始下标vectorintbuildSuffixArray(constvectorintnums){intnnums.size();vectorintsa(n),rank(n),tmp(n);// 初始排名按第一个元素for(inti0;in;i){sa[i]i;rank[i]nums[i];}// 倍增排序for(intk1;kn;k1){autocmp[](inti,intj){if(rank[i]!rank[j])returnrank[i]rank[j];intri(ikn)?rank[ik]:-1;intrj(jkn)?rank[jk]:-1;returnrirj;};sort(sa.begin(),sa.end(),cmp);tmp[sa[0]]0;for(inti1;in;i){tmp[sa[i]]tmp[sa[i-1]](cmp(sa[i-1],sa[i])?1:0);}ranktmp;if(rank[sa[n-1]]n-1)break;// 全部排名不同提前结束}returnsa;}// 计算 height 数组height[i] LCP(sa[i], sa[i-1])height[0] 0vectorintbuildHeight(constvectorintnums,constvectorintsa){intnnums.size();vectorintrank(n);for(inti0;in;i)rank[sa[i]]i;vectorintheight(n,0);inth0;for(inti0;in;i){if(rank[i]0){intjsa[rank[i]-1];while(ihnjhnnums[ih]nums[jh])h;height[rank[i]]h;if(h0)h--;}}returnheight;}intsmallestUniqueSubarray(constvectorintnums){intnnums.size();if(n0)return0;// 根据题意不会出现vectorintsabuildSuffixArray(nums);vectorintheightbuildHeight(nums,sa);intansn;for(inti0;in;i){// 当前后缀与左右相邻后缀的 LCP 最大值 1 即为最小唯一前缀长度intuniqueLenheight[i]1;if(in-1){uniqueLenmax(height[i],height[i1])1;}// 不能超过后缀自身长度if(uniqueLenn-sa[i]){ansmin(ans,uniqueLen);}}returnans;}intmain(){vectorintnums{3,3,3};intresultsmallestUniqueSubarray(nums);coutresultendl;return0;}