力扣Hot100速记

2025年5月10日 · 阅读需 8 分钟

Heng_Xin

ここから先は一方通行だ!

最近打算把 Hot100 给它肝了, 不过只是每日3题罢了...

有些题目二刷了, 之前会的, 现在还是得思考, 但是这种东西, 你思考你就输了...

故本博客会记录题目, 并且把题目的解法总结为短短的几句话或者图示, 以方便我复习 =-=

长期更新

1. 哈希

1. 两数之和

前缀和 (维护右枚举左), 秒了
49. 字母异位词分组

给每一个字符串排序后哈希加入分组, 然后再return; $O(n \times m \log{m} )$ , $m$ 是字符串长度

进阶的是使用 array<int, 26> 来记录数字然后哈希; $O(n m)$

更厉害的是使用质数表然后乘法, 这样可以直接拿数字哈希
128. 最长连续序列

在未排序的数组中, $O(n)$ 找到最长连续序列, 使用哈希集合, 枚举 $x$ 与 $x + 1$ 来不断 next; 维护最大长度, 剪枝就是先把全部数先放集合, 从而去重; 然后再判断 $x - 1$ 是否在集合, 如果在, 说明之前已经枚举过它了, 不会有更长的, 可以直接 continue 了

2. 双指针

283. 移动零

一个指针指向数字的后一个位置, 和一个不断变量的数字, 如果非0, 就和该指针交换位置, 并且指针++;

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int mae = 0;
        for (int& x : nums) {
            if (x) {
                swap(x, nums[mae]);
                ++mae;
            }
        }
    }
};
cpp

11. 盛最多水的容器

左右指针, 维护最高的柱子, 同时遍历过程中, 不断计算并维护当前的水的最大值; 移动左右的低的柱子

15. 三数之和

有很慢的 $O(n^2)$ 的哈希的维护右枚举左的写法.

正解应该是排序后双指针

class Solution {
    using ll = long long;
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 和为 0 的, 不重复的 (v1, v2, v3)
        int n = nums.size();
        vector<vector<int>> res;
        ranges::sort(nums); // 排序后, 定一, 然后就是 [有序版-两数之和]
        for (int i = 0; i < n - 2; ++i) {
            int v = nums[i];
            if (i && v == nums[i - 1]) // 去重
                continue;
            if (v + nums[i + 1] + nums[i + 2] > 0) // 剪枝: 当前 + 最小 > 0 => 不可能会 == 0
                break;
            if (v + nums[n - 1] + nums[n - 2] < 0) // 剪枝: 当前 + 最大 < 0 => 目前不会 == 0
                continue;
            int l = i + 1, r = n - 1, tg = -v;
            while (l < r) {
                int x = nums[l] + nums[r];
                if (x > tg) {
                    --r;
                } else if (x < tg) {
                    ++l;
                } else { // ==
                    int lv = nums[l], rv = nums[r];
                    res.push_back({v, lv, rv});
                    while (l < r && lv == nums[l]) // 去重
                        ++l;
                    while (l < r && rv == nums[r]) // 去重
                        --r;
                }
            }
        }
        return res;
    }
};
cpp

42. 接雨水

前缀和 + 后缀和罢了 (其中一个方法)

3. 滑动窗口

3. 无重复字符的最长子串

哈希表计数 + 滑窗即可
438. 找到字符串中所有字母异位词

哈希表计数字母 + 滑窗

4. 子串

560. 和为 K 的子数组

前缀和上的两数之和 (可维护右枚举左, 记得写等式推: $r - l = k \to l = r - k$ , 其中 $l, r$ 为前缀和的值)
239. 滑动窗口最大值

单调双端队列: {维护单调性 => 元素离开窗口 => 记录答案} for in nums 即可~

76. 最小覆盖子串

哈希计数字符个数 + 触发阈值的滑窗 (如果满足字符了 => 才开始减)

class Solution {
public:
    string minWindow(string s, string t) {
        auto hash = [](char c) -> int {
            return (c & ' ') ? c - 'a' : c - 'A' + 26;
        };
        array<int, 26 + 26> cntS{}, cntT{};
        for (char c : t)
            ++cntT[hash(c)];
        int n = s.size(), isOk = [&]{
            int res = 0;
            for (int v : cntT)
                res += v > 0;
            return res;
        }();
        int resBegin = 1e9, resLen = 1e9;
        for (int i = 0, l = 0; i < n; ++i) {
            int idx = hash(s[i]);
            if (++cntS[idx] == cntT[idx])
                --isOk;
            while (!isOk) {
                int jdx = hash(s[l]);
                if (cntS[jdx]-- == cntT[jdx]) {
                    ++isOk;
                    if (resBegin == (int)1e9 || i - l + 1 < resLen)
                        resBegin = l, resLen = i - l + 1;
                }
                ++l;
            }
        }
        return resBegin == (int)1e9
            ? ""
            : s.substr(resBegin, resLen);
    }
};
cpp

5. 普通数组

53. 最大子数组和

贪心/dp: 如果小于0, 就不选了, 然后维护这个过程中的最大值
56. 合并区间

排序后, 从头遍历, 看看是否答案的右端点是否大于当前的左端点, 如果是则更新当前答案的右端点的最大值, 如果否, 则答案新增一个区间
189. 轮转数组

如果不想额外空间, 那么就上结论吧: 答案 = 反转整个数组 + 反转 [0, k) + 反转 [k, n)

@todo: 有空把推导深入看看, 我用的是交换法, 有点难调, 发现答案是 gcd(k, n) 轮交换... 不是同一个算法吧~
238. 除自身以外数组的乘积

返回的数组做后缀积, 然后顺序再一次前缀积即可

41. 缺失的第一个正数

$O(n)$ 换座位: 假设 [1, n] 都在自己座位上, 如果 nums[i] 不在 i + 1 上, 说明位置不对, 给她换了:

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            // 在 [1, n] 内
            // nums[i] - 1 是因为索引从 0 开始
            // nums[nums[i] - 1] == nums[i]
            // 的前提是 nums[i] = i + 1
            while (nums[i] >= 1 
                && nums[i] <= n 
                && nums[nums[i] - 1] != nums[i]
            ) {
                // 交换: 把这里的换过去, 那里的也换过来
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        for (int i = 0; i < n; ++i) // 最终判断第一次 nums[i] != i + 1 的
            if (nums[i] != i + 1)   // 就是缺少 i + 1 号同学
                return i + 1;
        return n + 1;               // 否则就是都有; 缺 n + 1
    }
};
cpp