Enter your search text in the box above

Select a result to preview

LeetCode Hot 100 背诵笔记

官方题单：LeetCode 热题 100

单题笔记模板

每道题尽量保持简短：用一句话概括题意，用 2～4 条面试时可以直接复述的要点讲清思路，配上最优算法代码，并写明时间、空间复杂度。

> 说明：`0000` 是四位 LeetCode 题号的占位符，请替换为实际题号；例如第 1 题写作 `0001`。

### 0000 题目名称

题目链接：[LeetCode 0000 题目名称](题目链接)

> 核心题意：用一句话说明题目要求。

题解：[灵茶山爱府-LeetCode-0000](我提供给你的链接)

**解法思路：**
- 先说明最关键的观察或解题突破口。
- 再说明核心数据结构、算法和遍历过程。
- 最后说明为什么这样做，以及复杂度如何得到优化。

代码注释要求：只注释关键变量、核心步骤和边界处理，解释“为什么这样做”，避免逐行翻译代码。

```cpp
class Solution {
public:
    // 用一句话说明算法的核心做法
    ReturnType functionName(/* 参数 */) {
        // 关键变量：说明变量的含义和作用

        // 按照解法思路执行核心步骤

        return result;
    }
};
```

**时间和空间复杂度分析：**
- 时间复杂度：$O(?)$，简要说明原因。
- 空间复杂度：$O(?)$，简要说明原因。

哈希

0001 两数之和

题目链接：LeetCode 0001 两数之和

核心题意：在数组中找到两个不同位置的元素，使它们的和等于 target，返回这两个元素的下标。

题解：灵茶山爱府-LeetCode-0001

解法思路：

class Solution {
public:
    // 一边遍历，一边用哈希表查找当前数字所需要的另一个数
    vector<int> twoSum(vector<int>& nums, int target) {
        // value -> index：只记录已经遍历过的元素，方便 O(1) 查找补数
        unordered_map<int, int> idx;

        for (int i = 0; i < nums.size(); i++) {
            int x = nums[i];

            // 先查再存，保证匹配的是之前的元素，不会和自己重复使用
            auto it = idx.find(target - x);
            if (it != idx.end()) {
                return {it->second, i};
            }

            idx[x] = i;
        }

        return {};
    }
};

时间和空间复杂度分析：

0049 字母异位词分组

题目链接：LeetCode 0049 字母异位词分组

核心题意：把由相同字母组成、只是排列顺序不同的字符串分到同一组。

题解：灵茶山爱府-LeetCode-0049

解法思路：

class Solution {
public:
    // 把排序后的字符串作为分组标识，相同标识的字符串放到同一组
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // key：排序后的标准形式；value：属于这一组的所有原字符串
        unordered_map<string, vector<string>> groups;

        for (string& s : strs) {
            // 异位词包含完全相同的字符，因此排序后一定得到相同的 key
            string key = s;
            sort(key.begin(), key.end());

            groups[key].push_back(s);
        }

        vector<vector<string>> ans;

        // 每个 key 对应的字符串列表就是一组字母异位词
        for (auto& [_, group] : groups) {
            ans.push_back(move(group));
        }

        return ans;
    }
};

时间和空间复杂度分析：

0128 最长连续序列

题目链接：LeetCode 0128 最长连续序列

核心题意：在未排序数组中找到最长的连续整数序列，并返回它的长度，要求做到 O(n) 时间复杂度。

题解：灵茶山爱府-LeetCode-0128

解法思路：

class Solution {
public:
    // 只从连续序列的起点向后查找，避免对同一段序列重复扫描
    int longestConsecutive(vector<int>& nums) {
        // 去重，同时支持平均 O(1) 判断某个整数是否存在
        unordered_set<int> st(nums.begin(), nums.end());

        int ans = 0;

        for (int x : st) {
            // x-1 存在说明前面还有数字，x 不是起点，从这里扫描会产生重复
            if (st.contains(x - 1)) {
                continue;
            }

            // x 是起点，从这里一直向右扩展到连续序列的末尾
            int y = x + 1;
            while (st.contains(y)) {
                y++;
            }

            // 序列为 [x, y-1]，长度正好是 y-x
            ans = max(ans, y - x);
        }

        return ans;
    }
};

时间和空间复杂度分析：

双指针

0283 移动零

题目链接：LeetCode 0283 移动零

核心题意：原地把数组中的所有 0 移到末尾，同时保持所有非零元素的相对顺序不变。

题解：灵茶山爱府-LeetCode-0283

解法思路：

class Solution {
public:
    // 快指针寻找非零元素，慢指针记录下一个非零元素应放的位置
    void moveZeroes(vector<int>& nums) {
        int i0 = 0; // [0, i0) 已经是处理好的非零元素

        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 0) {
                // 把当前非零元素放到前面，原来的 0 被交换到后面
                swap(nums[i], nums[i0]);
                i0++;
            }
        }
    }
};

时间和空间复杂度分析：

0011 盛最多水的容器

题目链接：LeetCode 0011 盛最多水的容器

核心题意：从数组中选择两根竖线，使它们和横轴围成的容器面积最大。

题解：灵茶山爱府-LeetCode-0011

解法思路：

class Solution {
public:
    // 从最大宽度开始，每次淘汰较短的那根柱子
    int maxArea(vector<int>& height) {
        int ans = 0;
        int left = 0, right = height.size() - 1;

        while (left < right) {
            int area = (right - left) * min(height[left], height[right]);
            ans = max(ans, area);

            // 宽度必然减小，只有换掉较短边才可能得到更大的面积
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return ans;
    }
};

时间和空间复杂度分析：

0015 三数之和

题目链接：LeetCode 0015 三数之和

核心题意：找出数组中所有和为 0 且不重复的三元组。

题解：灵茶山爱府-LeetCode-0015

解法思路：

class Solution {
public:
    // 排序后固定第一个数，用相向双指针寻找另外两个数
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        vector<vector<int>> ans;
        int n = nums.size();

        for (int i = 0; i < n - 2; i++) {
            // 相同的第一个数会产生重复三元组
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // 当前三个最小值已经大于 0，后面不可能再有答案
            if (nums[i] + nums[i + 1] + nums[i + 2] > 0) {
                break;
            }

            // 当前数和最大的两个数仍小于 0，当前 nums[i] 太小
            if (nums[i] + nums[n - 2] + nums[n - 1] < 0) {
                continue;
            }

            int left = i + 1, right = n - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum < 0) {
                    left++;
                } else if (sum > 0) {
                    right--;
                } else {
                    ans.push_back({nums[i], nums[left], nums[right]});

                    // 找到答案后跳过重复的第二、第三个数
                    for (left++; left < right && nums[left] == nums[left - 1]; left++);
                    for (right--; left < right && nums[right] == nums[right + 1]; right--);
                }
            }
        }

        return ans;
    }
};

时间和空间复杂度分析：

0042 接雨水

题目链接：LeetCode 0042 接雨水

核心题意：给定每根柱子的高度，计算下雨后这些柱子之间一共能够接住多少水。

题解：灵茶山爱府-LeetCode-0042

解法思路：

class Solution {
public:
    // 双指针同时维护左右最大高度，谁的最大高度小就计算谁
    int trap(vector<int>& height) {
        int ans = 0;
        int left = 0, right = height.size() - 1;
        int preMax = 0, sufMax = 0;

        while (left < right) {
            // 分别维护 [0, left] 和 [right, n-1] 的最大高度
            preMax = max(preMax, height[left]);
            sufMax = max(sufMax, height[right]);

            if (preMax < sufMax) {
                // 右侧一定存在不低于 preMax 的墙，左侧水位已经确定
                ans += preMax - height[left];
                left++;
            } else {
                // 左侧一定存在不低于 sufMax 的墙，右侧水位已经确定
                ans += sufMax - height[right];
                right--;
            }
        }

        return ans;
    }
};

时间和空间复杂度分析：

滑动窗口

0003 无重复字符的最长子串

题目链接：LeetCode 0003 无重复字符的最长子串

核心题意：找出字符串中不包含重复字符的最长连续子串，并返回其长度。

题解：灵茶山爱府-LeetCode-0003

解法思路讲解：

class Solution {
public:
    // 滑动窗口维护一个没有重复字符的最长区间
    int lengthOfLongestSubstring(string s) {
        int n = s.length(), ans = 0, left = 0;

        // 记录当前窗口中每个字符的出现次数
        unordered_map<char, int> cnt;

        for (int right = 0; right < n; right++) {
            char c = s[right];
            cnt[c]++;

            // c 重复时缩小左边界，直到窗口重新合法
            while (cnt[c] > 1) {
                cnt[s[left]]--;
                left++;
            }

            ans = max(ans, right - left + 1);
        }

        return ans;
    }
};

时间和空间复杂度分析：

0438 找到字符串中所有字母异位词

题目链接：LeetCode 0438 找到字符串中所有字母异位词

核心题意：在字符串 s 中找到所有与 p 字母出现次数完全相同的长度为 p.size() 的子串，并返回这些子串的起始下标。

题解：灵茶山爱府-LeetCode-0438

解法思路讲解：

class Solution {
public:
    // 定长滑窗维护长度为 p.size() 的子串，并比较字符出现次数
    vector<int> findAnagrams(string s, string p) {
        array<int, 26> cnt_s{};
        array<int, 26> cnt_p{};
        vector<int> ans;

        // 目标频率：p 中每个字母需要出现多少次
        for (char c : p) {
            cnt_p[c - 'a']++;
        }

        int m = p.length();

        for (int right = 0; right < s.length(); right++) {
            // 当前字符进入窗口
            cnt_s[s[right] - 'a']++;

            int left = right - m + 1;

            // 窗口长度还不足 m，暂时不检查
            if (left < 0) {
                continue;
            }

            if (cnt_s == cnt_p) {
                ans.push_back(left);
            }

            // 检查完成后移除左端字符，为下一个窗口做准备
            cnt_s[s[left] - 'a']--;
        }

        return ans;
    }
};

时间和空间复杂度分析：

子串

0560 和为 K 的子数组

题目链接：LeetCode 0560 和为 K 的子数组

核心题意：统计数组中元素和恰好等于 k 的连续子数组个数。

题解：灵茶山爱府-LeetCode-0560

解法思路讲解：

class Solution {
public:
    // 一边计算前缀和，一边用哈希表统计满足 s[j] - s[i] = k 的左端点数量
    int subarraySum(vector<int>& nums, int k) {
        int ans = 0, s = 0;

        // 空前缀 s[0] = 0 出现一次
        unordered_map<int, int> cnt{{0, 1}};

        for (int x : nums) {
            s += x;

            // 若之前出现过 s-k，则这些位置都可以作为当前子数组的左边界
            ans += cnt.contains(s - k) ? cnt[s - k] : 0;

            // 当前前缀和只能供后面的元素使用，所以最后再加入哈希表
            cnt[s]++;
        }

        return ans;
    }
};

时间和空间复杂度分析：

0239 滑动窗口最大值

题目链接：LeetCode 0239 滑动窗口最大值

核心题意：维护长度为 k 的滑动窗口，并返回每个窗口中的最大值。

题解：灵茶山爱府-LeetCode-0239

解法思路讲解：

class Solution {
public:
    // 用单调递减队列维护当前窗口中可能成为最大值的元素下标
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        deque<int> q;

        for (int right = 0; right < nums.size(); right++) {
            // 当前元素更大且更晚出现，队尾较小元素以后不可能成为最大值
            while (!q.empty() && nums[q.back()] <= nums[right]) {
                q.pop_back();
            }
            q.push_back(right);

            int left = right - k + 1;

            // 队首已经不属于当前窗口
            if (q.front() < left) {
                q.pop_front();
            }

            // 窗口形成后，队首就是当前窗口最大值
            if (left >= 0) {
                ans.push_back(nums[q.front()]);
            }
        }

        return ans;
    }
};

时间和空间复杂度分析：

0076 最小覆盖子串

题目链接：LeetCode 0076 最小覆盖子串

核心题意：在 s 中找到包含 t 所有字符及其对应出现次数的最短连续子串。

题解：灵茶山爱府-LeetCode-0076

解法思路讲解：

class Solution {
    bool is_covered(int cnt_s[], int cnt_t[]) {
        for (int i = 'A'; i <= 'Z'; i++) {
            if (cnt_s[i] < cnt_t[i]) {
                return false;
            }
        }
        for (int i = 'a'; i <= 'z'; i++) {
            if (cnt_s[i] < cnt_t[i]) {
                return false;
            }
        }
        return true;
    }

public:
    string minWindow(string s, string t) {
        int cnt_s[128]{}; // s 子串字母的出现次数
        int cnt_t[128]{}; // t 中字母的出现次数
        for (char c : t) {
            cnt_t[c]++;
        }

        int m = s.size();
        int ans_left = -1, ans_right = m;
        int left = 0;

        for (int right = 0; right < m; right++) { // 移动子串右端点
            cnt_s[s[right]]++; // 右端点字母移入子串
            while (is_covered(cnt_s, cnt_t)) { // 涵盖
                if (right - left < ans_right - ans_left) { // 找到更短的子串
                    ans_left = left; // 记录此时的左右端点
                    ans_right = right;
                }
                cnt_s[s[left]]--; // 左端点字母移出子串
                left++;
            }
        }

        return ans_left < 0 ? "" : s.substr(ans_left, ans_right - ans_left + 1);
    }
};

时间和空间复杂度分析：

普通数组

0053 最大子数组和

题目链接：LeetCode 0053 最大子数组和

核心题意：找出数组中和最大的非空连续子数组，并返回这个最大和。

题解：灵茶山爱府-LeetCode-0053

解法思路讲解：

class Solution {
public:
    // 枚举子数组右端点，用当前前缀和减去此前的最小前缀和
    int maxSubArray(vector<int>& nums) {
        int ans = INT_MIN;
        int pre_sum = 0;
        int min_pre_sum = 0; // 当前右端点之前的最小前缀和

        for (int x : nums) {
            pre_sum += x;
            ans = max(ans, pre_sum - min_pre_sum);

            // 必须在计算答案之后更新，保证子数组非空
            min_pre_sum = min(min_pre_sum, pre_sum);
        }

        return ans;
    }
};

时间和空间复杂度分析：

0056 合并区间

题目链接：LeetCode 0056 合并区间

核心题意：将所有存在重叠的区间合并，返回最终互不重叠的区间集合。

题解：灵茶山爱府-LeetCode-0056

解法思路讲解：

class Solution {
public:
    // 按左端点排序后，只需和最后一个已合并区间比较
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        ranges::sort(intervals);

        vector<vector<int>> ans;
        for (auto& p : intervals) {
            if (!ans.empty() && p[0] <= ans.back()[1]) {
                // 有重叠，只需要扩大右端点
                ans.back()[1] = max(ans.back()[1], p[1]);
            } else {
                ans.emplace_back(p);
            }
        }

        return ans;
    }
};

时间和空间复杂度分析：

0189 轮转数组

题目链接：LeetCode 0189 轮转数组

核心题意：将数组中的元素整体向右轮转 k 个位置，并要求原地修改数组。

题解：灵茶山爱府-LeetCode-0189

解法思路讲解：

class Solution {
public:
    // 整体反转，再分别反转两部分，实现原地右轮转
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;

        reverse(nums.begin(), nums.end());

        // 恢复原数组最后 k 个元素的内部顺序
        reverse(nums.begin(), nums.begin() + k);

        // 恢复其余元素的内部顺序
        reverse(nums.begin() + k, nums.end());
    }
};

时间和空间复杂度分析：

0238 除了自身以外数组的乘积

题目链接：LeetCode 0238 除了自身以外数组的乘积

核心题意：对于每个位置 i，计算数组中除 nums[i] 外所有元素的乘积，且不能使用除法。

题解：灵茶山爱府-LeetCode-0238

解法思路讲解：

class Solution {
public:
    // 答案 = 左侧所有元素乘积 × 右侧所有元素乘积
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, 1);

        // ans[i] 先保存 nums[i] 左侧所有元素的乘积
        for (int i = 1; i < n; i++) {
            ans[i] = ans[i - 1] * nums[i - 1];
        }

        int suf = 1; // 当前下标右侧所有元素的乘积
        for (int i = n - 1; i >= 0; i--) {
            ans[i] *= suf;
            suf *= nums[i];
        }

        return ans;
    }
};

时间和空间复杂度分析：

0041 缺失的第一个正数

题目链接：LeetCode 0041 缺失的第一个正数

核心题意：在未排序数组中找出没有出现的最小正整数，并要求 O(n) 时间、O(1) 额外空间。

题解：灵茶山爱府-LeetCode-0041

解法思路讲解：

class Solution {
public:
    // 把值 x 原地放到下标 x-1，使数组本身充当哈希表
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();

        for (int i = 0; i < n; i++) {
            // 当前数字合法且目标座位还没坐着同一个数字，就继续换座位
            while (1 <= nums[i] && nums[i] <= n &&
                   nums[i] != nums[nums[i] - 1]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }

        // 第一个没有坐对人的座位，就是缺失的最小正整数
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        return n + 1;
    }
};

时间和空间复杂度分析：

矩阵

0073 矩阵置零

题目链接：LeetCode 0073 矩阵置零

核心题意：如果矩阵中某个元素为 0，就把它所在的整行和整列全部置为 0，并要求原地修改。

题解：灵茶山爱府-LeetCode-0073

解法思路讲解：

class Solution {
public:
    // 用第一行和第一列记录哪些行、列最终需要置零
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();

        bool row0 = false;
        bool col0 = false;

        // 第一行和第一列后面会被当作标记，因此先保存它们原本是否含 0
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                row0 = true;
            }
        }
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                col0 = true;
            }
        }

        // 用第一列标记行，用第一行标记列
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        // 根据标记处理内部元素
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // 最后处理第一行和第一列，避免提前修改标记
        if (row0) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
        if (col0) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
};

时间和空间复杂度分析：

0054 螺旋矩阵

题目链接：LeetCode 0054 螺旋矩阵

核心题意：按照右、下、左、上的顺时针螺旋顺序，返回矩阵中的所有元素。

题解：灵茶山爱府-LeetCode-0054

解法思路讲解：

class Solution {
public:
    // 按右、下、左、上的方向循环，并不断缩短每次需要走的步数
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int size = m * n;

        const int DIRS[4][2] = {
            {0, 1},   // 右
            {1, 0},   // 下
            {0, -1},  // 左
            {-1, 0}   // 上
        };

        vector<int> ans;
        int i = 0, j = -1; // 从第一行左侧出发，使第一次移动直接进入 (0,0)

        for (int d = 0; ans.size() < size; d = (d + 1) % 4) {
            for (int k = 0; k < n; k++) {
                i += DIRS[d][0];
                j += DIRS[d][1];
                ans.push_back(matrix[i][j]);
            }

            // 下一方向的步数依次为 n, m-1, n-1, m-2...
            int tmp = n;
            n = m - 1;
            m = tmp;
        }

        return ans;
    }
};

时间和空间复杂度分析：

0048 旋转图像

题目链接：LeetCode 0048 旋转图像

核心题意：将一个 n×n 矩阵原地顺时针旋转 90∘。

题解：灵茶山爱府-LeetCode-0048

解法思路讲解：

class Solution {
public:
    // 先沿主对角线转置，再将每一行左右翻转
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();

        // 只遍历上三角，避免交换两次又恢复原状
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }

        // 转置后的每一行再左右翻转
        for (auto& row : matrix) {
            reverse(row.begin(), row.end());
        }
    }
};

时间和空间复杂度分析：

0240 搜索二维矩阵 II

题目链接：LeetCode 0240 搜索二维矩阵 II

核心题意：在每行、每列都递增的矩阵中，高效判断是否存在目标值 target。

题解：灵茶山爱府-LeetCode-0240

解法思路讲解：

class Solution {
public:
    // 从右上角开始，每次比较排除一整行或一整列
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();

        int i = 0;
        int j = n - 1; // 当前搜索区域的右上角

        while (i < m && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            }

            if (matrix[i][j] > target) {
                // 当前列往下只会更大，因此整列可以排除
                j--;
            } else {
                // 当前行往左只会更小，因此整行可以排除
                i++;
            }
        }

        return false;
    }
};

时间和空间复杂度分析：

链表

二叉树

图论

回溯

二分查找

栈

堆

贪心算法

动态规划

多维动态规划

技巧