企业官网建设流程全解析

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完整代码如下：

packagemainimport("fmt""index/suffixarray""unsafe")funcmax(a,bint)int{ifa>b{returna}returnb}funcmin(a,bint)int{ifa<b{returna}returnb}funcsmallestUniqueSubarray(nums[]int)int{n:=len(nums)// 将每个整数拆成 3 个字节，用于构造后缀数组tmp:=make([]byte,0,n*3)for_,x:=rangenums{tmp=append(tmp,byte(x>>16),byte(x>>8),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%3==0{sa=append(sa,p/3)}}// 后缀名次数组 rankrank:=make([]int,n)fori,p:=rangesa{rank[p]=i}// 高度数组 height（LCP 数组）height:=make([]int,n)h:=0fori,rk:=rangerank{ifh>0{h--}ifrk>0{forj:=int(sa[rk-1]);i+h<n&&j+h<n&&nums[i+h]==nums[j+h];h++{}}height[rk]=h}ans:=nfori,h:=rangeheight{// 该后缀与左右相邻后缀的 LCP 最大值 +1 即为最小唯一前缀长度uniqueLength:=h+1ifi<n-1{uniqueLength=max(h,height[i+1])+1}ifuniqueLength<=n-int(sa[i]){ans=min(ans,uniqueLength)}}returnans}funcmain(){nums:=[]int{3,3,3}result:=smallestUniqueSubarray(nums)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-defbuild_suffix_array(nums):"""构建整数数组的后缀数组（倍增算法）"""n=len(nums)ifn==1:return[0]# 初始排名：直接用数值（但需注意数值可能较大，排序时依然正确）rank=list(nums)sa=list(range(n))k=1tmp=[0]*nwhileTrue:# 按 (rank[i], rank[i+k] if i+k<n else -1) 排序sa.sort(key=lambdai:(rank[i],rank[i+k]ifi+k<nelse-1))tmp[sa[0]]=0foriinrange(1,n):prev,cur=sa[i-1],sa[i]prev_key=(rank[prev],rank[prev+k]ifprev+k<nelse-1)cur_key=(rank[cur],rank[cur+k]ifcur+k<nelse-1)tmp[cur]=tmp[prev]+(1ifcur_key!=prev_keyelse0)rank,tmp=tmp,rank# 交换，tmp 变为旧 rank（后续会被覆盖）ifrank[sa[-1]]==n-1:# 所有排名都不同breakk<<=1returnsadefbuild_lcp(nums,sa):"""计算 LCP 数组（height），height[i] = LCP(sa[i], sa[i-1])，height[0]=0"""n=len(nums)rank=[0]*nfori,pinenumerate(sa):rank[p]=i height=[0]*n h=0foriinrange(n):ifrank[i]>0:j=sa[rank[i]-1]whilei+h<nandj+h<nandnums[i+h]==nums[j+h]:h+=1height[rank[i]]=hifh>0:h-=1returnheightdefsmallest_unique_subarray(nums):n=len(nums)ifn==0:return0sa=build_suffix_array(nums)height=build_lcp(nums,sa)ans=nforiinrange(n):# 当前后缀与左右相邻后缀的 LCP 最大值 +1 即为最小唯一前缀长度unique_len=height[i]+1ifi<n-1:unique_len=max(height[i],height[i+1])+1# 不能超过后缀自身的长度ifunique_len<=n-sa[i]:ans=min(ans,unique_len)returnansif__name__=="__main__":nums=[3,3,3]result=smallest_unique_subarray(nums)print(result)

C++完整代码如下：

#include<iostream>#include<vector>#include<algorithm>#include<string>usingnamespacestd;// 构建后缀数组 sa，sa[i] 表示第 i 小的后缀的起始下标vector<int>buildSuffixArray(constvector<int>&nums){intn=nums.size();vector<int>sa(n),rank(n),tmp(n);// 初始排名：按第一个元素for(inti=0;i<n;i++){sa[i]=i;rank[i]=nums[i];}// 倍增排序for(intk=1;k<n;k<<=1){autocmp=[&](inti,intj){if(rank[i]!=rank[j])returnrank[i]<rank[j];intri=(i+k<n)?rank[i+k]:-1;intrj=(j+k<n)?rank[j+k]:-1;returnri<rj;};sort(sa.begin(),sa.end(),cmp);tmp[sa[0]]=0;for(inti=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;// 全部排名不同，提前结束}returnsa;}// 计算 height 数组，height[i] = LCP(sa[i], sa[i-1])，height[0] = 0vector<int>buildHeight(constvector<int>&nums,constvector<int>&sa){intn=nums.size();vector<int>rank(n);for(inti=0;i<n;i++)rank[sa[i]]=i;vector<int>height(n,0);inth=0;for(inti=0;i<n;i++){if(rank[i]>0){intj=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--;}}returnheight;}intsmallestUniqueSubarray(constvector<int>&nums){intn=nums.size();if(n==0)return0;// 根据题意不会出现vector<int>sa=buildSuffixArray(nums);vector<int>height=buildHeight(nums,sa);intans=n;for(inti=0;i<n;i++){// 当前后缀与左右相邻后缀的 LCP 最大值 +1 即为最小唯一前缀长度intuniqueLen=height[i]+1;if(i<n-1){uniqueLen=max(height[i],height[i+1])+1;}// 不能超过后缀自身长度if(uniqueLen<=n-sa[i]){ans=min(ans,uniqueLen);}}returnans;}intmain(){vector<int>nums={3,3,3};intresult=smallestUniqueSubarray(nums);cout<<result<<endl;return0;}