【美团3.18校招真题1】

大厂笔试真题网址：https://codefun2000.com/

塔子哥刷题网站博客：https://blog.codefun2000.com/

小美剪彩带

提交网址：https://codefun2000.com/p/P1088

题意：找出区间内不超过k种数字子数组的最大长度

使用双指针的方式，用哈希表来统计每个数出现次数。在双指针移动的过程中，动态的维护区间内不同数个数。具体的，当右端点遇到一个新的数时map的记录+1，当左端点删去一个只出现一次的数时map的记录-1，在这个过程中统计窗口最大值即可

首先用r指针不断往map中添加数据，直到map中的数据多于k个，此时让mp.size() = k + 1的元素4已经放入了mp，且r又++了（此时元素5还没放入map），不算map中最后放入的那个元素，map正好存放的是存放k种数字的所有元素

即r-1指向让mp.size() = k + 1的元素，r - 2指向最后一个让mp.size() = k的元素，需要计算 [l,r - 2] 区间长度

map中数据过多后，l指针右移，直到区间内数据不大于k，如此往复直到r越界

当r不断向右移动的过程中，若map没有先满，而是r越界了，此时情况不一样，需要记录的 [l,r - 1] 区间长度

#include<iostream>
#include<vector>
#include<unordered_map>using namespace std;int main() {int n, k;cin >> n >> k;if (k == 0) return 0;vector<int> nums(n, 0);for (int i = 0; i < n; i++) cin >> nums[i];int l = 0;int r = 0;int ans = 0;unordered_map<int, int> mp;  // <val, freq>while (r < n) {while (r < n && (int)mp.size() <= k) {mp[nums[r]]++;r++;}if ((int)mp.size() > k) {// 如果是因为mp装入太多数了，导致已经大于k了，退出while// 说明让mp.size() = k + 1的nums[r]已经放入了mp，且r又++了，需要减去1ans = max(ans, r - l - 1);}else {// 肯定是因为r == n了，mp.size()依然<=k，[l, r)区间内都是满足的ans = max(ans, r - l);break;}while (l <= r && (int)mp.size() > k) {mp[nums[l]]--;if (mp[nums[l]] == 0) mp.erase(nums[l]);l++;}}cout << ans << endl;return 0;
}

map中始终存放[l,r]区间内的数据，mp.size() <= k时不断右移 r 指针，mp.size()一旦大于k，就需要右移 l 指针

int main() {int n, k;cin >> n >> k;if (k == 0) return 0;vector<int> nums(n, 0);for (int i = 0; i < n; i++) cin >> nums[i];int l = 0;int r = 0;int ans = 0;// <val, freq>// 始终存放[l,r]区间内的数据，mp.size()一旦大于k，就需要移动l指针unordered_map<int, int> mp;  while (r < n) {mp[nums[r]]++;while (mp.size() > k) {mp[nums[l]]--;if (mp[nums[l]] == 0) mp.erase(nums[l]);l++;}ans = max(ans, r - l + 1);r++;}cout << ans << endl;return 0;
}