HashMap

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

1
2
3
4
5
6
7
8
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);
    }
};

2841. 几乎唯一子数组的最大和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    long long maxSum(vector<int> &nums, int m, int k) {
        long long ans = 0, sum = 0;
        unordered_map<int, int> cnt;
        for (int i = 0; i < k - 1; i++) { // 先统计 k-1 个数
            sum += nums[i];
            cnt[nums[i]]++;//处理前两个元素：cnt = {1: 1, 2: 1}
        }
        for (int i = k - 1; i < nums.size(); i++) {
            sum += nums[i]; // 再添加一个数就是 k 个数了
            cnt[nums[i]]++;
            if (cnt.size() >= m)
                ans = max(ans, sum);

            int out = nums[i - k + 1];
            sum -= out; // 下一个子数组不包含 out，移出窗口
            if (--cnt[out] == 0)
                cnt.erase(out);//删除元素
        }
        return ans;
    }
};

1297. 子串的最大出现次数

substr()操作和unordered_set的用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
        unordered_map<string, int> cnt;
        int ans=0;
        for (int i = 0; i < s.length() - minSize + 1; i++) {
            string str = s.substr(i, minSize);
            unordered_set<char> exist(str.begin(), str.end());

            if (exist.size() <= maxLetters)
            {
                cnt[str] ++ ;
                ans = max(ans, cnt[str]);
            }
        }
        return ans;
    }
    
};
排序算法 最坏时间复杂度 最优时间复杂度 平均时间复杂度 空间复杂度
插入排序（Insertion Sort, IS） O(n^2) O(n) O(n^2) O(1)
自顶向下归并排序（MergeX） O(n log n) O(n log n) O(n log n) O(n)
自底向上归并排序（MergeBU） O(n log n) O(n log n) O(n log n) O(n)
随机快速排序（Quick） O(n^2) O(n log n) O(n log n) O(log n)
三向划分快速排序（Quick3way） O(n^2) O(n log n) O(n log n) O(log n)