2026-05-09：不同元素和至少为 K 的最短子数组长度。用go话语，给定一个整数数组 nums 和一个整数 k。你需要在数组中找一个邻接的非空子数组，使得这个子数组里不同元素的种类数对应的取值之和（也即是：每个数只算一次，不访佛计）不小于 k。求知足要求的最短子数组长度；若是不存在这么的子数组，就复返 -1。

1

1

1

输入： 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，幸运飞艇app2026世界杯中国官方下载0]，长度1，不知足要求

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

1. 把 2 加入窗口：cnt[2] = 2

2. 2 依然出现过，sum 不变化 → sum=2

3. 判断 sum(2) ≥ 4？不知足，不收缩窗口

4. 现时窗口：[0，1]，长度2，金沙JinSha(中国)娱乐网入口不知足要求

第三步：右指针 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

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

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

def minLength(nums， k):

cnt = {}

sum_val = 0

left = 0

ans = math.inf

for i， x in enumerate(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

using namespace 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

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

return 0;

}

咱们深信东谈主工智能为庸俗东谈主提供了一种“增强器用”，并勤劳于共享全见识的AI常识。在这里，您不错找到最新的AI科普著述、器用评测、普及成果的隐痛以及行业细察。

接待眷注“福大大架构师逐日一题”金沙JinSha(中国)娱乐网，发音讯可得回口试贵府，让AI助力您的改日发展。