LeetCode 1852. 每個子數組的數字種類數(滑窗)

Michael阿明 2021-08-15 22:28:32 阅读数:421

本文一共[544]字,预计阅读时长:1分钟~
leetcode

文章目錄

1. 題目

給你一個整數數組 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]'1','2','3'三種數字所以 ans[0] = 3
- nums[1:3] = [2,3,2]'2','3'兩種數字所以 ans[1] = 2
- nums[2:4] = [3,2,2]'2','3'兩種數字所以 ans[2] = 2
- nums[3:5] = [2,2,1]'1','2'兩種數字所以 ans[3] = 2
- nums[4:6] = [2,1,3]'1','2','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] 只有'1'這一種數字所以 ans[0] = 1
- nums[1:4] = [1,1,1,2]'1','2'兩種數字所以 ans[1] = 2
- nums[2:5] = [1,1,2,3]'1','2','3'三種數字所以 ans[2] = 3
- nums[3:6] = [1,2,3,4]'1','2','3','4'四種數字所以 ans[3] = 4
提示:
1 <= k <= nums.length <= 10^5
1 <= nums[i] <= 10^5

來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/distinct-numbers-in-each-subarray
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。

2. 解題

  • 滑動窗口
class Solution {

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

int n = nums.size();
vector<int> ans(n-k+1);
unordered_map<int,int> m;
for(int i = 0; i < k; ++i)
{

m[nums[i]]++;
}
ans[0] = m.size();
for(int i = k; i < n; ++i)
{

if(--m[nums[i-k]] == 0)
m.erase(nums[i-k]);
++m[nums[i]];
ans[i-k+1] = m.size();
}
return ans;
}
};

376 ms 134.9 MB C++


我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號(Michael阿明),一起加油、一起學習進步!
Michael阿明

版权声明:本文为[Michael阿明]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815222753173E.html