滑动窗口
滑动窗口的思路是很容易想到的,但是在移动窗口的过程中,如果每次都判断当前是否存在重复元素显得效率低下。此时一种优化的思路是:窗口中数字变化无非来自左边元素的删除和右边元素的增加,只有删除了正好出现两次的元素,或者增加了正好出现一次的元素,才会导致窗口内重复元素种类的变化。显然重复元素种类大于0时,窗口内存在重复元素为真,可以维护这个种类数量来判断是否存在重复元素。
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param s string字符串
* @param k int整型
* @return int整型
*/
int numKLenSubstrRepeats(string s, int k) {
int n = s.size();
unordered_map<char, int> num_count;
int count = 0;
for (int i = 0; i < k; ++i) {
++num_count[s[i]];
}
for (auto it = num_count.begin(); it != num_count.end(); ++it) {
if (it->second > 1) {
++count;
}
}
int ans = 0;
if (count) {
++ans;
}
for (int i = k; i < n; ++i) {
--num_count[s[i-k]];
if (num_count[s[i-k]] == 1) {
--count;
}
++num_count[s[i]];
if (num_count[s[i]] == 2) {
++count;
}
if (count) {
++ans;
}
}
return ans;
}
};