Medium

题目描述

给你一个整数数组 nums 和一个整数 k。

返回子数组的最小长度，该子数组中不同值的和（每个值只计算一次）至少为 k。如果不存在这样的子数组，返回 -1。

示例 1：

输入：nums = [2,2,3,1], k = 4
输出：2
解释：
子数组 [2, 3] 包含不同元素 {2, 3}，它们的和是 2 + 3 = 5，至少为 k = 4。因此，答案是 2。

示例 2：

输入：nums = [3,2,3,4], k = 5
输出：2
解释：
子数组 [3, 2] 包含不同元素 {3, 2}，它们的和是 3 + 2 = 5，至少为 k = 5。因此，答案是 2。

示例 3：

输入：nums = [5,5,4], k = 5
输出：1
解释：
子数组 [5] 包含不同元素 {5}，它们的和是 5，至少为 k = 5。因此，答案是 1。

约束条件：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5
  • 1 <= k <= 10^9

解题思路

这道题要求找到最短子数组，使得其中不同元素的和至少为 k。关键在于理解"不同元素的和"指的是每个值只计算一次。

核心思路： 使用滑动窗口技术配合哈希表来维护窗口内元素的频次。当某个元素的频次为 1 时，它对"不同元素和"有贡献；当频次大于 1 时，只贡献一次。

算法步骤：

  1. 使用双指针 left 和 right 维护滑动窗口
  2. 用哈希表记录每个元素在当前窗口中的出现次数
  3. 维护一个变量 distinctSum 表示当前窗口的不同元素和
  4. 扩展右边界：当加入新元素时，如果该元素首次出现，则将其值加到 distinctSum 中
  5. 收缩左边界：当 distinctSum >= k 时，尝试收缩左边界来找最小长度
  6. 移除元素时，如果该元素的频次变为 0，则从 distinctSum 中减去其值

推荐解法： 使用滑动窗口 + 哈希表，时间复杂度最优。

通过这种方法，我们可以在一次遍历中找到满足条件的最短子数组。

代码实现

class Solution {
public:
    int minLength(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        long long distinctSum = 0;
        int left = 0, minLen = INT_MAX;
        
        for (int right = 0; right < nums.size(); right++) {
            // 扩展右边界
            if (freq[nums[right]] == 0) {
                distinctSum += nums[right];
            }
            freq[nums[right]]++;
            
            // 收缩左边界
            while (distinctSum >= k) {
                minLen = min(minLen, right - left + 1);
                freq[nums[left]]--;
                if (freq[nums[left]] == 0) {
                    distinctSum -= nums[left];
                }
                left++;
            }
        }
        
        return minLen == INT_MAX ? -1 : minLen;
    }
};

class Solution:
    def minLength(self, nums: List[int], k: int) -> int:
        freq = {}
        distinct_sum = 0
        left = 0
        min_len = float('inf')
        
        for right in range(len(nums)):
            # 扩展右边界
            if nums[right] not in freq or freq[nums[right]] == 0:
                distinct_sum += nums[right]
                freq[nums[right]] = 0
            freq[nums[right]] += 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

public class Solution {
    public int MinLength(int[] nums, int k) {
        Dictionary<int, int> freq = new Dictionary<int, int>();
        long distinctSum = 0;
        int left = 0, minLen = int.MaxValue;
        
        for (int right = 0; right < nums.Length; right++) {
            // 扩展右边界
            if (!freq.ContainsKey(nums[right])) {
                freq[nums[right]] = 0;
            }
            if (freq[nums[right]] == 0) {
                distinctSum += nums[right];
            }
            freq[nums[right]]++;
            
            // 收缩左边界
            while (distinctSum >= k) {
                minLen = Math.Min(minLen, right - left + 1);
                freq[nums[left]]--;
                if (freq[nums[left]] == 0) {
                    distinctSum -= nums[left];
                }
                left++;
            }
        }
        
        return minLen == int.MaxValue ? -1 : minLen;
    }
}

var minLength = function(nums, k) {
    let minLen = Infinity;
    
    for (let i = 0; i < nums.length; i++) {
        let distinctSet = new Set();
        let distinctSum = 0;
        
        for (let j = i; j < nums.length; j++) {
            if (!distinctSet.has(nums[j])) {
                distinctSet.add(nums[j]);
                distinctSum += nums[j];
            }
            
            if (distinctSum >= k) {
                minLen = Math.min(minLen, j - i + 1);
                break;
            }
        }
    }
    
    return minLen === Infinity ? -1 : minLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(min(n, m))

其中 n 是数组长度，m 是不同元素的个数。每个元素最多被访问两次（一次加入，一次移除），哈希表的空间取决于不同元素的数量。