大多数题解，都是在哈希表中存储字符串。类似如下的代码：

class Solution {
public:
    bool hasAllCodes(string s, int k) {

        unordered_set<string> set;
        for(int i = 0; i + k <= s.size(); i ++) set.insert(s.substr(i, k));
        return set.size() == (1 << k);
    }
};

但其实，这样做，因为哈希表中存的是长度为 k 的子串。每次计算子串的哈希值，是需要 O(k) 的时间的。所以这个算法真正的复杂度是 O(|s| * k)

我提交的数据是这样的：

这个问题可以优化，我们可以使用滑动窗口的思想，每次把长度为 k 的子串所对应的整数计算出来。之后，每次窗口向前移动，子串最高位丢掉一个字符；最低位添加一个字符，使用 O(1) 的时间即可计算出新的数字。同时，哈希表中存储的是整型，复杂度才是真正的 O(1)。整体算法复杂度是 O(|s|)的。

class Solution {
public:
    bool hasAllCodes(string s, int k) {

        if(k > s.size()) return 0;

        int cur = 0;
        for(int i = 0; i < k - 1; i ++)
            cur = 2 * cur + (s[i] == '1');

        unordered_set<int> set;
        for(int i = k - 1; i < s.size(); i ++){
            cur = cur * 2 + (s[i] == '1');
            set.insert(cur);
            cur &= ~(1 << (k - 1));
        }
        return set.size() == (1 << k);
    }
};

上面的代码在 leetcode 上测试，时间快一倍，空间消耗也更少。

最后，如果使用整型，我们就可以不再使用哈希表了，直接把数组当哈希表用，索引即是 key。这样，性能又能提升一倍。

class Solution {
public:
    bool hasAllCodes(string s, int k) {

        if(k > s.size()) return 0;

        int cur = 0;
        for(int i = 0; i < k - 1; i ++)
            cur = 2 * cur + (s[i] == '1');

        vector<bool> used(1 << k, false);
        for(int i = k - 1; i < s.size(); i ++){
            cur = cur * 2 + (s[i] == '1');
            used[cur] = true;
            cur &= ~(1 << (k - 1));
        }
        
        for(int e: used) if(!e) return false;
        return true;
    }
};