苏州新区建网站,商务网站前台模板,做一个像美团的网站需要多少钱,微信官方网站建设大厂笔试真题网址#xff1a;https://codefun2000.com/
塔子哥刷题网站博客#xff1a;https://blog.codefun2000.com/
小美剪彩带
提交网址#xff1a;https://codefun2000.com/p/P1088 题意#xff1a;找出区间内不超过k种数字子数组的最大长度
使用双指针的方式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] 区间长度
#includeiostream
#includevector
#includeunordered_mapusing namespace std;int main() {int n, k;cin n k;if (k 0) return 0;vectorint nums(n, 0);for (int i 0; i n; i) cin nums[i];int l 0;int r 0;int ans 0;unordered_mapint, int mp; // val, freqwhile (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;vectorint 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_mapint, 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;
}
