Distinct Numbers in Each Subarray
给一个数组和一个数字k, 求数组中k大小的subarray的不同的数字的个数.
用map当滑窗计算一下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Solution { public: vector<int> distinctNumbers(vector<int>& nums, int k) { vector<int> res; int n = nums.size(); unordered_map<int, int> map; for(int i = 0; i < n; i++){ if(i < k){ map[nums[i]]++; }else{ res.push_back(map.size()); map[nums[i - k]]--; if(map[nums[i - k]] == 0){ map.erase(nums[i - k]); } map[nums[i]]++; } } res.push_back(map.size()); return res; } }; |