滑动窗口

滑动窗口的思路是很容易想到的,但是在移动窗口的过程中,如果每次都判断当前是否存在重复元素显得效率低下。此时一种优化的思路是:窗口中数字变化无非来自左边元素的删除和右边元素的增加,只有删除了正好出现两次的元素,或者增加了正好出现一次的元素,才会导致窗口内重复元素种类的变化。显然重复元素种类大于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;
    }
};