3795. 不同元素和至少为 K 的最短子数组长度

🎯 问题描述（来源于LeetCode）

描述：
给定一个整数数组 nums 和一个整数 k。你需要找一个连续的非空子数组，使得该子数组中不同元素的和（即去重后的元素之和）至少为 k。
返回满足条件的最短子数组长度。如果不存在这样的子数组，返回 -1。

说明：

子数组必须连续。
求和时，重复出现的元素只计算一次。
子数组中可以包含重复元素。

示例：

示例 1：

1
2
3

输入: nums = [1,2,3,1,1], k = 5
输出: 3
解释: 子数组 [1,2,3] 的不同元素和为 1+2+3=6 ≥ 5，长度为 3。

示例 2：

1
2
3

输入: nums = [2,3,1,2,4,3], k = 7
输出: 3
解释: 子数组 [2,3,1] 的不同元素和为 2+3+1=6 < 7；[2,3,1,2] 的不同元素和为 2+3+1=6 < 7；[3,1,2,4] 的不同元素和为 3+1+2+4=10 ≥ 7，长度为 4；[1,2,4] 的不同元素和为 1+2+4=7 ≥ 7，长度为 3，是最短的。

示例 3：

1
2
3

输入: nums = [1,1,1,1], k = 2
输出: -1
解释: 所有不同元素只有 1，和为 1 < 2，无法达到。

💻 解题思路

思路：滑动窗口（双指针）+ 哈希表统计频率

算法步骤

初始化左指针 left = 0，频率字典 freq（记录窗口内每个元素的出现次数），变量 distinct_sum（记录窗口内不同元素的数值之和）。
初始化最小长度 min_len = inf。
遍历右指针 right，将 nums[right] 加入窗口：
- 如果该元素在窗口内首次出现（freq[num] == 0），则将该元素的值加到 distinct_sum。
- 更新频率 freq[num] += 1。
当 distinct_sum >= k 时，尝试缩小窗口：
- 更新 min_len = min(min_len, right - left + 1)。
- 将左指针元素移出窗口：freq[nums[left]] -= 1。
- 如果该元素的频率变为 0，则从 distinct_sum 中减去该元素的值。
- 左指针右移 left += 1。
若 min_len 仍为 inf，返回 -1；否则返回 min_len。

代码实现（您的代码）

from collections import Counter
from typing import List

class Solution:
    def minLength(self, nums: List[int], k: int) -> int:
        left = 0
        freq = Counter()
        distinct_sum = 0
        min_len = float('inf')
        for right, num in enumerate(nums):
            if freq[num] == 0:
                distinct_sum += num
            freq[num] += 1
            while distinct_sum >= k:
                min_len = min(min_len, right - left + 1)
                freq[nums[left]] -= 1
                if freq[nums[left]] == 0:
                    distinct_sum -= nums[left]
                left += 1
        return min_len if min_len != float('inf') else -1