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

福大大架构师每日一题

发布于 2026-05-09 13:55:28

300

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 <iostream>
#include <vector>
#include <unordered_map>
#include <climits>
#include <algorithm>

usingnamespace std;

int minLength(vector<int>& nums, int k) {
    unordered_map<int, int> 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<int> nums = {2, 2, 3, 1};
    int k = 4;
    int result = minLength(nums, k);
    cout << result << endl;
    return0;
}