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. 1.cnt：哈希表，記錄窗口內每個數字出現的次數

2. 2.sum：記錄窗口內不同元素的和（每個數字只加一次，重復出現不加）

3. 3.left：滑動窗口的左邊界指針

4. 4.ans：記錄滿足條件的最短子數組長度，初始為無窮大

5. 5.i（右指針）：滑動窗口的右邊界指針

數組：[2, 2, 3, 1]，目標和 k=4
初始狀態：cnt=空，sum=0，left=0，ans=無窮大

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

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

2. 2. 因為是第一次出現 2，sum += 2→ sum=2

3. 3. 判斷 sum(2) ≥ 4？不滿足，不收縮窗口

4. 4. 當前窗口：[0,0]，長度1，不滿足條件

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

2. 2. 2 已經出現過，sum 不變化 → sum=2

3. 3. 判斷 sum(2) ≥ 4？不滿足，不收縮窗口

4. 4. 當前窗口：[0,1]，長度2，不滿足條件

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

2. 2. 第一次出現 3，sum += 3→ sum=5

3. 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. 把 1 加入窗口：cnt[1] = 1

2. 2. 第一次出現 1，sum += 1→ sum=4

3. 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萬 長度的數組

• ? 僅使用了一個哈希表cnt存儲窗口內的不同元素

• ? 哈希表的最大存儲量 = 數組中不同元素的個數

• ? 總額外空間復雜度：O(n)（最壞情況數組元素全不同）

1. 1. 執行過程：右指針擴展窗口累加不同元素和，滿足條件后左指針收縮窗口，同步記錄最小長度；

2. 2. 時間復雜度：O(n)，適合大數據量；

3. 3. 額外空間復雜度：O(n)，用于存儲窗口內元素計數。

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助力您的未來發展。