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，世界杯滚球app中国官方下载0]，长度1，不悦足条款

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

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

2. 2 照旧出现过，sum 不变化 → sum=2

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

4. 现时窗口：[0，1]，长度2，开云官网入口 - 开云kaiyun(中国)官网不悦足条款

第三步：右指针 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科普著作、器用评测、擢升效果的诡秘以及行业知悉。

迎接关爱“福大大架构师逐日一题”开云kaiyun(中国)官网，发音书可赢得口试贵府，让AI助力您的将来发展。