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

package main

 import (
    "fmt"
    "math"
)

 func minLength(nums []int, k int)int {
    cnt := map[int]int{}
    sum := 0
    left := 0
    ans := math.MaxInt

     for i, x := range nums {
        // 1. 入
        cnt[x]++
        if cnt[x] == 1 {
            sum += x
        }

         for sum >= k {
            // 2. 更新答案
            ans = min(ans, i-left+1)

             // 3. 出
            out := nums[left]
            cnt[out]--
            if cnt[out] == 0 {
                sum -= out
            }
            left++
        }
    }

     if ans == math.MaxInt {
        return-1
    }
    return ans
}

 func main() {
    nums := []int{2, 2, 3, 1}
    k := 4
    result := minLength(nums, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 import math

 defminLength(nums, k):
    cnt = {}
    sum_val = 0
    left = 0
    ans = math.inf

     for i, x inenumerate(nums):
        # 1. 入
        cnt[x] = cnt.get(x, 0) + 1
        if cnt[x] == 1:
            sum_val += x

         while sum_val >= k:
            # 2. 更新答案
            ans = min(ans, i - left + 1)

             # 3. 出
            out_val = nums[left]
            cnt[out_val] -= 1
            if cnt[out_val] == 0:
                sum_val -= out_val
            left += 1

     if ans == math.inf:
        return -1
    return ans

 if __name__ == "__main__":
    nums = [2, 2, 3, 1]
    k = 4
    result = minLength(nums, k)
    print(result)

C++完整代码如下：

#include  

#include  

#include  

#include  

#include  


 usingnamespace std;

 int minLength(vector& nums, int k) {
    unordered_map cnt;
    int sum = 0;
    int left = 0;
    int ans = INT_MAX;

     for (int i = 0; i < nums.size(); i++) {
        int x = nums[i];

         // 1. 入
        cnt[x]++;
        if (cnt[x] == 1) {
            sum += x;
        }

         while (sum >= k) {
            // 2. 更新答案
            ans = min(ans, i - left + 1);

             // 3. 出
            int out_val = nums[left];
            cnt[out_val]--;
            if (cnt[out_val] == 0) {
                sum -= out_val;
            }
            left++;
        }
    }

     if (ans == INT_MAX) {
        return-1;
    }
    return ans;
}

 int main() {
    vector nums = {2, 2, 3, 1};
    int k = 4;
    int result = minLength(nums, k);
    cout << result << endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。