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

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;
    }
};

最终函数优化

Last modification:June 2nd, 2020 at 10:22 am
如果你觉得我的文章帮助到了你,请随意赞赏~