列表

详情

1852. 每个子数组的数字种类数

给你一个整数数组 nums与一个整数 k，请你构造一个长度 n-k+1 的数组 ans，这个数组第i个元素 ans[i] 是每个长度为k的子数组 nums[i:i+k-1] = [nums[i], nums[i+1], ..., nums[i+k-1]]中数字的种类数。

返回这个数组 ans。

 

示例 1:

输入: nums = [1,2,3,2,2,1,3], k = 3
输出: [3,2,2,2,3]
解释：每个子数组的数字种类计算方法如下：
- nums[0:2] = [1,2,3] 所以 ans[0] = 3
- nums[1:3] = [2,3,2] 所以 ans[1] = 2
- nums[2:4] = [3,2,2] 所以 ans[2] = 2
- nums[3:5] = [2,2,1] 所以 ans[3] = 2
- nums[4:6] = [2,1,3] 所以 ans[4] = 3

示例 2:

输入: nums = [1,1,1,1,2,3,4], k = 4
输出: [1,2,3,4]
解释: 每个子数组的数字种类计算方法如下：
- nums[0:3] = [1,1,1,1] 所以 ans[0] = 1
- nums[1:4] = [1,1,1,2] 所以 ans[1] = 2
- nums[2:5] = [1,1,2,3] 所以 ans[2] = 3
- nums[3:6] = [1,2,3,4] 所以 ans[3] = 4

 

提示:

原站题解

去查看

class Solution {
public:
vector<int> distinctNumbers(vector<int>& nums, int k) {
}
};
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

cpp 解法, 执行用时: 200 ms, 内存消耗: 98.8 MB, 提交时间: 2023-10-22 11:02:31 

class Solution {

public:

    vector<int> distinctNumbers(vector<int>& nums, int k) {

        // 不同数字的计数

        int cnt[100001];

        memset(cnt, 0, sizeof(cnt));

        // 记录昂前窗口里的不同的数量

        int diff = 0;

        for (int i = 0; i < k; ++i)

        {

            diff += cnt[nums[i]] == 0;

            ++cnt[nums[i]];

        }



        int n = nums.size();

        vector<int> res(n-k+1, 0);

        res[0] = diff;

        int i = 0;

        for (int j = k; j < n; ++j)

        {

            // 按照不同结果去调整diff数量

            if (cnt[nums[j]]++ == 0)

            {

                ++diff;

            }

            if (--cnt[nums[i]] == 0)

            {

                --diff;

            }

            res[++i] = diff;

        }



        return res;

    }

};

java 解法, 执行用时: 7 ms, 内存消耗: 55.9 MB, 提交时间: 2023-10-22 11:02:13 

class Solution {

    public int[] distinctNumbers(int[] nums, int k) {

        int n = nums.length, size = 0;

        int[] aux = new int[100_001];

        for (int i=0; i<k; i++) {

            if (aux[nums[i]]==0) size++;

            aux[nums[i]]++;

        }

        int[] ans = new int[n-k+1];

        ans[0] = size;

        for (int j=k, i=0; j<n; j++) {

            if (aux[nums[j]]++==0) size++;

            if (--aux[nums[i]]==0) size--;

            ans[++i] = size;

        }

        return ans;

    }

}

python3 解法, 执行用时: 248 ms, 内存消耗: 34 MB, 提交时间: 2023-10-22 11:01:59 

class Solution:

    def distinctNumbers(self, nums: List[int], k: int) -> List[int]:

        mp = collections.defaultdict(int)

        for i in range(k):

            mp[nums[i]] +=1

        ans = [len(mp)]

        for i in range(k, len(nums)):

            f, l = nums[i-k], nums[i]

            if mp[f] == 1:

                del mp[f]

            else:

                mp[f] -=1

            mp[l] +=1

            ans.append(len(mp))

        return ans

上一题

© 2025 leetcode.cn