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时，尝试收缩左指针缩小窗口，同时记录满足条件的最小窗口长度。整个过程只遍历数组一次，保证高效性。

关键变量说明

1. cnt：哈希表，记录窗口内每个数字出现的次数
2. sum：记录窗口内不同元素的和（每个数字只加一次，重复出现不加）
3. left：滑动窗口的左边界指针
4. ans：记录满足条件的最短子数组长度，初始为无穷大
5. i（右指针）：滑动窗口的右边界指针

逐步骤执行过程

数组：[2, 2, 3, 1]，目标和 k=4
初始状态：cnt=空，sum=0，left=0，ans=无穷大

第一步：右指针 i=0，元素 x=2

1. 把 2 加入窗口：cnt[2] = 1
2. 因为是第一次出现 2，sum += 2→ sum=2
3. 判断 sum(2) ≥ 4？不满足，不收缩窗口
4. 当前窗口：[0,0]，长度1，不满足条件

第二步：右指针 i=1，元素 x=2

1. 把 2 加入窗口：cnt[2] = 2
2. 2 已经出现过，sum 不变化 → sum=2
3. 判断 sum(2) ≥ 4？不满足，不收缩窗口
4. 当前窗口：[0,1]，长度2，不满足条件

第三步：右指针 i=2，元素 x=3

1. 把 3 加入窗口：cnt[3] = 1
2. 第一次出现 3，sum += 3→ sum=5
3. 判断 sum(5) ≥ 4？满足条件，开始收缩左指针：
   • 更新最短长度：ans = min(无穷大, 2-0+1=3) → ans=3
   • 移出左边界元素 2：cnt[2] = 1
   • 2 还在窗口中，sum 不变 → sum=5
   • 左指针右移：left=1
4. 再次判断 sum(5) ≥ 4？仍满足，继续收缩：
   • 更新最短长度：ans = min(3, 2-1+1=2) → ans=2
   • 移出左边界元素 2：cnt[2] = 0，2 彻底离开窗口
   • sum 减去 2 → sum=3
   • 左指针右移：left=2
5. 此时 sum=3 < 4，停止收缩
6. 当前窗口：[2,2]，长度1，不满足条件

第四步：右指针 i=3，元素 x=1

1. 把 1 加入窗口：cnt[1] = 1
2. 第一次出现 1，sum += 1→ sum=4
3. 判断 sum(4) ≥ 4？满足条件，开始收缩左指针：
   • 更新最短长度：ans = min(2, 3-2+1=2) → ans 保持 2
   • 移出左边界元素 3：cnt[3] = 0，3 彻底离开窗口
   • sum 减去 3 → sum=1
   • 左指针右移：left=3
4. 此时 sum=1 < 4，停止收缩
5. 当前窗口：[3,3]，长度1，不满足条件

最终结果

遍历完整个数组后，ans=2（不是无穷大），返回结果 2。

时间复杂度 & 空间复杂度

1. 时间复杂度

• 右指针从头到尾遍历数组一次，共执行 n 次（n 为数组长度）
• 左指针只会向右移动，不会回退，整个过程最多执行 n 次
• 哈希表的增、删、查操作都是O(1)常数时间
• 总时间复杂度：O(n)（线性时间），能高效处理 10万 长度的数组

2. 额外空间复杂度

• 仅使用了一个哈希表cnt存储窗口内的不同元素
• 哈希表的最大存储量 = 数组中不同元素的个数
• 总额外空间复杂度：O(n)（最坏情况数组元素全不同）

总结

1. 执行过程：右指针扩展窗口累加不同元素和，满足条件后左指针收缩窗口，同步记录最小长度；
2. 时间复杂度：O(n)，适合大数据量；
3. 额外空间复杂度：O(n)，用于存储窗口内元素计数。

Go完整代码如下：

packagemainimport("fmt""math")funcminLength(nums[]int,kint)int{cnt:=map[int]int{}sum:=0left:=0ans:=math.MaxIntfori,x:=rangenums{// 1. 入cnt[x]++ifcnt[x]==1{sum+=x}forsum>=k{// 2. 更新答案ans=min(ans,i-left+1)// 3. 出out:=nums[left]cnt[out]--ifcnt[out]==0{sum-=out}left++}}ifans==math.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_val=0left=0ans=math.inffori,xinenumerate(nums):# 1. 入cnt[x]=cnt.get(x,0)+1ifcnt[x]==1:sum_val+=xwhilesum_val>=k:# 2. 更新答案ans=min(ans,i-left+1)# 3. 出out_val=nums[left]cnt[out_val]-=1ifcnt[out_val]==0:sum_val-=out_val left+=1ifans==math.inf:return-1returnansif__name__=="__main__":nums=[2,2,3,1]k=4result=minLength(nums,k)print(result)

C++完整代码如下：

#include<iostream>#include<vector>#include<unordered_map>#include<climits>#include<algorithm>usingnamespacestd;intminLength(vector<int>&nums,intk){unordered_map<int,int>cnt;intsum=0;intleft=0;intans=INT_MAX;for(inti=0;i<nums.size();i++){intx=nums[i];// 1. 入cnt[x]++;if(cnt[x]==1){sum+=x;}while(sum>=k){// 2. 更新答案ans=min(ans,i-left+1);// 3. 出intout_val=nums[left];cnt[out_val]--;if(cnt[out_val]==0){sum-=out_val;}left++;}}if(ans==INT_MAX){return-1;}returnans;}intmain(){vector<int>nums={2,2,3,1};intk=4;intresult=minLength(nums,k);cout<<result<<endl;return0;}