2026-05-09：不同元素和至少为 K 的最短子数组长度。用go语言，给定一个整数数组 nums 和一个整数 k。你需要在数组中找一个连续的非空子数组，使得这个子数组里不同元素的种类数对应的取值之

2026-05-09不同元素和至少为 K 的最短子数组长度。用go语言给定一个整数数组 nums 和一个整数 k。你需要在数组中找一个连续的非空子数组使得这个子数组里不同元素的种类数对应的取值之和也就是每个数只算一次不重复计不小于 k。求满足条件的最短子数组长度如果不存在这样的子数组就返回 -1。1 nums.length 100000。1 nums[i] 100000。1 k 1000000000。输入 nums [2,2,3,1], k 4。输出 2。解释子数组 [2, 3] 具有不同的元素 {2, 3}它们的和为 2 3 5这至少为 k 4。因此答案是 2。题目来自力扣3795。算法执行过程详细描述核心思路我们使用滑动窗口双指针算法用左、右两个指针界定一个连续的窗口右指针不断向右扩展窗口把元素加入窗口当窗口内不同元素的和 ≥ k时尝试收缩左指针缩小窗口同时记录满足条件的最小窗口长度。整个过程只遍历数组一次保证高效性。关键变量说明cnt哈希表记录窗口内每个数字出现的次数sum记录窗口内不同元素的和每个数字只加一次重复出现不加left滑动窗口的左边界指针ans记录满足条件的最短子数组长度初始为无穷大i右指针滑动窗口的右边界指针逐步骤执行过程数组[2, 2, 3, 1]目标和 k4初始状态cnt空sum0left0ans无穷大第一步右指针 i0元素 x2把 2 加入窗口cnt[2] 1因为是第一次出现 2sum 2→ sum2判断 sum(2) ≥ 4不满足不收缩窗口当前窗口[0,0]长度1不满足条件第二步右指针 i1元素 x2把 2 加入窗口cnt[2] 22 已经出现过sum 不变化 → sum2判断 sum(2) ≥ 4不满足不收缩窗口当前窗口[0,1]长度2不满足条件第三步右指针 i2元素 x3把 3 加入窗口cnt[3] 1第一次出现 3sum 3→ sum5判断 sum(5) ≥ 4满足条件开始收缩左指针更新最短长度ans min(无穷大, 2-013) → ans3移出左边界元素 2cnt[2] 12 还在窗口中sum 不变 → sum5左指针右移left1再次判断 sum(5) ≥ 4仍满足继续收缩更新最短长度ans min(3, 2-112) → ans2移出左边界元素 2cnt[2] 02 彻底离开窗口sum 减去 2 → sum3左指针右移left2此时 sum3 4停止收缩当前窗口[2,2]长度1不满足条件第四步右指针 i3元素 x1把 1 加入窗口cnt[1] 1第一次出现 1sum 1→ sum4判断 sum(4) ≥ 4满足条件开始收缩左指针更新最短长度ans min(2, 3-212) → ans 保持 2移出左边界元素 3cnt[3] 03 彻底离开窗口sum 减去 3 → sum1左指针右移left3此时 sum1 4停止收缩当前窗口[3,3]长度1不满足条件最终结果遍历完整个数组后ans2不是无穷大返回结果 2。时间复杂度 空间复杂度1. 时间复杂度右指针从头到尾遍历数组一次共执行 n 次n 为数组长度左指针只会向右移动不会回退整个过程最多执行 n 次哈希表的增、删、查操作都是O(1)常数时间总时间复杂度O(n)线性时间能高效处理 10万 长度的数组2. 额外空间复杂度仅使用了一个哈希表cnt存储窗口内的不同元素哈希表的最大存储量 数组中不同元素的个数总额外空间复杂度O(n)最坏情况数组元素全不同总结执行过程右指针扩展窗口累加不同元素和满足条件后左指针收缩窗口同步记录最小长度时间复杂度O(n)适合大数据量额外空间复杂度O(n)用于存储窗口内元素计数。Go完整代码如下packagemainimport(fmtmath)funcminLength(nums[]int,kint)int{cnt:map[int]int{}sum:0left:0ans:math.MaxIntfori,x:rangenums{// 1. 入cnt[x]ifcnt[x]1{sumx}forsumk{// 2. 更新答案ansmin(ans,i-left1)// 3. 出out:nums[left]cnt[out]--ifcnt[out]0{sum-out}left}}ifansmath.MaxInt{return-1}returnans}funcmain(){nums:[]int{2,2,3,1}k:4result:minLength(nums,k)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-importmathdefminLength(nums,k):cnt{}sum_val0left0ansmath.inffori,xinenumerate(nums):# 1. 入cnt[x]cnt.get(x,0)1ifcnt[x]1:sum_valxwhilesum_valk:# 2. 更新答案ansmin(ans,i-left1)# 3. 出out_valnums[left]cnt[out_val]-1ifcnt[out_val]0:sum_val-out_val left1ifansmath.inf:return-1returnansif__name____main__:nums[2,2,3,1]k4resultminLength(nums,k)print(result)C完整代码如下#includeiostream#includevector#includeunordered_map#includeclimits#includealgorithmusingnamespacestd;intminLength(vectorintnums,intk){unordered_mapint,intcnt;intsum0;intleft0;intansINT_MAX;for(inti0;inums.size();i){intxnums[i];// 1. 入cnt[x];if(cnt[x]1){sumx;}while(sumk){// 2. 更新答案ansmin(ans,i-left1);// 3. 出intout_valnums[left];cnt[out_val]--;if(cnt[out_val]0){sum-out_val;}left;}}if(ansINT_MAX){return-1;}returnans;}intmain(){vectorintnums{2,2,3,1};intk4;intresultminLength(nums,k);coutresultendl;return0;}