ebb6bd124ee440cab48c47a7395956d3.png

【题目】：1461. 检查一个字符串是否包含所有长度为 K 的二进制子串

直接存储滑动窗口内的字符串，这样虽然方便，但是时间复杂度和k相关，如果k = n，此时会达到O(n^2)的复杂度。

cpp
class Solution {
public:
    bool hasAllCodes(string s, int k) {
        unordered_set<string> ss;
        for(int l = 0, r = 0; r < s.size(); ++r) {
            if(r - l + 1 == k) {
                ss.insert(s.substr(l, k));
                l++;
            }
        }
        return ss.size() == 1<<k;
    }
};
  • 时间复杂度: O(n*k)
  • 空间复杂度: O(1<<k)

1<<k：相当于pow(2, k)
substr(截取的字符串起始位置, 截取字符串的长度)