logoChat01.ai

给你一个整数数组 nums 和一个整数 k。 返回一个 子数组 的 最小 长度，使得该子数组中出现...

Créé le : 3 janvier 2026

Répondu en utilisant GPT-5.2 Thinking par Chat01

Question

给你一个整数数组 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 class Solution {
public int minLength(int[] nums, int k) {

}

}解决这个问题，通过所有例子，并不能超时

Réflexion

Analyzing minimal subarray problem with sliding window

I’m thinking through an algorithm for finding the minimal length of a subarray where the sum of distinct values is at least k. It seems like using a sliding window with two pointers could work: expanding the window to add new distinct values and shrinking when sums meet the criteria.

Refining sliding window algorithm

I’ve figured out that for the distinct sum, when I extend the right, it’s always non-decreasing. With this monotonic property, I can use a two-pointer approach: expand right, then shrink left to minimize the length while still satisfying the condition. I’m using an array for frequency counts to optimize performance.

Clarifying edge cases and sliding window approach

I’m considering the case where k might be less than or equal to 0. Since k >= 1 is the expected input, when k <= 0, the minimal subarray length should be 1, but that’s not the correct behavior here. The sliding window approach works if sumDistinct is monotonic, so it will find the minimal subarray length. Let’s verify with examples.

Thought for 19s

Réponse

思路：双指针/滑动窗口 + 计数数组维护“窗口内不同值之和”。

  • 用 freq[x] 表示当前窗口内值 x 出现次数
  • 用 sumDistinct 表示窗口内不同值的和（某个值只要出现过一次就计入一次）
  • 右指针扩展：加入 nums[r]，若 freq[val]==0，说明是新值，sumDistinct += val
  • 当 sumDistinct >= k 时，尽量收缩左指针来缩短长度，并更新答案；移除左端元素时若次数变 0，则 sumDistinct -= val

因为 nums[i] > 0，右扩展不会让 sumDistinct 变小，左收缩不会让它变大，所以滑动窗口正确且总复杂度 O(n)。

java
import java.util.*;

class Solution {
    public int minLength(int[] nums, int k) {
        int n = nums.length;
        int[] freq = new int[100001]; // nums[i] <= 1e5
        long sumDistinct = 0L;
        int ans = Integer.MAX_VALUE;

        int left = 0;
        for (int right = 0; right < n; right++) {
            int v = nums[right];
            if (freq[v] == 0) sumDistinct += v;
            freq[v]++;

            while (left <= right && sumDistinct >= k) {
                ans = Math.min(ans, right - left + 1);

                int lv = nums[left];
                freq[lv]--;
                if (freq[lv] == 0) sumDistinct -= lv;
                left++;
            }
        }

        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

复杂度：

  • 时间：O(n)（每个元素最多进窗口一次、出窗口一次）
  • 空间：O(U)，U=1e5（计数数组）

Partager cette Q&R