LeetCode Hot100解题笔记 260130更新

博主： 2810873701@qq.com
发布时间：2025 年 12 月 15 日
154 次浏览
暂无评论
38368字数
分类：算法工作学习

前言

有点惊讶吧？这个Hot100解题笔记还是提前到来了。因为呢，dp题单实在是太多了，然后面试题又有大部分都出现在Hot100里面。我的目标是把hot100刷个2遍左右，所以我准备现在抢跑：将dp题单和hot100同时往前推(在文章创建的时候是这样的，后面我猜可能dp会先停下来，然后继续推hot100)。

话不多说，下面直接开始解题！

PS：下面的数字格式是序号-力扣的题目编号，解题语言默认cpp。

1-1 两数之和

题目链接：https://leetcode.cn/problems/two-sum/description/?envType=study-plan-v2&envId=top-100-liked
难度：简单
解题日期：2025.12.15
标签：数组哈希表

虽说这是一道简单题，直接套双重循环也能过，但是这样总是差点意思。我是看了一眼题目的提示才知道要用哈希表(注意！unordered_map才是哈希表，map不是！)。

基本逻辑就是，利用哈希表查找速度O(1)的特性，把数组和下标对应丢进映射，然后遍历数组，将target与当前元素作差，然后在映射里面查找这个：如果找得到，就取出两个下标返回；如果找不到，就接着往下找，总能找到的。

然后呢，题目不允许取同一个下标两次，所以还得在取出下标的时候判断一下是否和当前下标相等，不然不能取。

至于你们可能担心的数组有重复数字的问题，不用担心，下面的代码在写映射的时候默认保留的是那个数字最大的下标，而我们遍历是从前往后遍历的，就算这是唯一解也凑得出。是不是有点bug+bug=没有bug的感觉了哈哈哈

上代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> dict;
        //1.给数字-下标对放进哈希映射
        for (int i=0;i<nums.size();i++) {
            dict[nums[i]] = i;
        }
        //2.遍历找搭配
        for (int i=0;i<nums.size();i++) {
            int x = target-nums[i];
            if (dict.count(x)>0 && dict[x]!=i) {
                return vector<int>{i,dict[x]}; //题目说返回顺序随意，所以我就懒得排序了
            }
        }
        return vector<int>{0,0}; //这一行是为了防止报错，题目用例保证有且只有一个答案，所以不会走到这里的
    }
};

2-49 字母异位词分组

题目链接：https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-100-liked
难度：中等
解题日期：2025.12.15
标签：数组哈希表字符串排序

这题还是挺有意思的，你看标签就知道了，需要先把每个字符串排序，这样才能知道它们互相之间是不是字母异位词。

那么怎么排序呢？

我目前学过的语言有Python，Go，Cpp这三个，其中前两者的字符串(string)类型都是不可变的，但是cpp的string属实是让我大开眼界了：不但可变(支持用sort排序)，而且还能拿来作为哈希表映射的键(可哈希)，这写起来不要太舒适。

所以，用cpp做这道题，直接遍历一遍字符串数组，然后对每个字符串直接使用sort就行了，非常方便。

然后下面的逻辑可能稍微有点绕，我干讲也不太好讲，直接在注释里面和代码一起讲好了。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        //1.拷贝一份字符串数组，并给每个字符串排序
        auto strs2 = strs; //这里用于存放唯一的字母异位词，大概率会出现一堆重复的字符串(从题目的用例来看)
        for (auto & s : strs2) {
            sort(s.begin(),s.end());
        }
        //2.使用哈希表管理二维数组的插入和下标管理
        unordered_map<string,int> dict; //这个映射存放已经插入的字符串在ans数组中的位置
        vector<vector<string>> ans; //存放答案的二维数组
        //这里用位置遍历是利用了strs和strs2的唯一字母异位词与原字符串的对齐，方便取出原字符串
        for (int i=0;i<strs.size();i++) {
            if (dict.count(strs2[i])==0) { //如果在dict里面没找到这个唯一的字母异位词，说明是新创建
                dict[strs2[i]]=ans.size(); //将这一系列字母异位词在ans数组中的位置存进dict
                ans.emplace_back(vector<string>{strs[i]}); //然后插入新的一行字符串数组
            } else { //如果有，只需找到对应的下标然后插入即可
                ans[dict[strs2[i]]].emplace_back(strs[i]); 
                //从dict中取出这一系列的字母异位词所在的ans数组的下标，然后插入最新的字母异位词
            }
        }
        return ans;
    }
};

看懂了吧？总结一下，就是利用排序后strs2数组中的字母异位词的唯一性，将其与strs中的原字符串相匹配，再配合映射进行它在ans二维数组中插入位置的管理，从而形成了有点小绕的逻辑闭环。

3-283 移动零

题目链接：https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=top-100-liked
难度：简单
解题日期：2025.12.16
标签：数组双指针

好久没做双指针的题目了，虽说这道题的难度是简单，并且我看到题目没几秒钟就想到了用额外空间该怎么做。

但是题目要求原地修改数组。我真求你了。

然后我又想了一会，想出了用一个指针找0，另一个指针负责把后面的元素一个个往前挪到前面的指针指向的位置把0盖掉，纯纯的用时间复杂度换空间复杂度，我真没招了。

然后咨询了一下ai，也算是回到了正轨：使用快慢指针模型来解决这道题目。

啥是快慢指针模型？

“快慢指针 - 读写模型”（或者叫“填充/覆盖模型”）：
快指针 (Reader)：负责读数据，判断这个数据要不要保留。
慢指针 (Writer)：负责写数据，始终指向“下一个有效数据的存放位置”。

在这道题目里面，快指针(下面统称为fast)负责寻找非0元素，而慢指针(下面统称为slow)负责寻找fast指针找到的非0元素的存放位置。

基本逻辑是这样的：fast一直往后挪，不停，所以直接用for循环就行；slow只有在fast找到非0元素时，才会将fast和slow所指元素交换，然后往后挪一位。

并且，这个设计非常精妙，保证了当发生交换时只有以下两种情况：要么是slow指向0，fast指向非0，要么是fast和slow一起指向同一个非0元素，也就是进行了"原地交换"，无事发生。

这是如何保证的呢？因为在上面的逻辑里面，假设当前fast和slow都指向一个非0元素，而下一个元素就是0，然后按照逻辑，fast和slow都往后挪一位，此时slow就自然指向了0。然后呢，由于fast是一直往后的，所以下一轮循环，由于fast指向了0，所以，slow不会往后。这样自然而然，就使得fast指向非0而slow指向了0。也可以这么理解：slow只是正在维护非0元素的边界(有点像插入排序，都是维护已处理-未处理的边界)。

当 fast 和 slow 错开时，slow 和 fast 中间夹着的那个区域（即 nums[slow...fast-1]），全都是 0。这就解释了为什么要把 nums[fast] 换过来——因为要把中间的这堆 0 往后挤！

这样逻辑就很清楚了吧？看代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slow=0;
        for (int fast=0;fast<nums.size();fast++) {
            if (nums[fast]!=0) { //只有遇到非0才会往后挪slow
                swap(nums[fast],nums[slow]);
                slow++;
            }
        }
    }
};

总结：一旦遇到数组原地筛选/移除/移动类题目，直接套用：Fast 找目标，Slow 守坑位。

4-128 最长连续序列

题目链接：https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked
难度：中等
解题日期：2025.12.17
标签：并查集数组哈希表

这是STL库被资本(LeetCode)做局的一题。

这道题的思路是很简单的：利用哈希表查询速度O(1)的特性，将本来O(n^2)的双指针暴力查询降级到O(n)的时间复杂度。

首先给所有元素都丢进unordered_set里面，顺带着还自动去重；然后呢，遍历nums数组，利用集合的count方法，另外开一个循环查询集合里面是否有当前元素x+1,x+2...x+n，由此得出长度就是n。

但是呢，这样会产生大量无用的查询：我后面遍历到x+1，亦或是x+2，甚至到x+n，都会重新执行一遍这个逻辑，给时间复杂度又退化成O(n^2)了，这可不行。

解决方法也很简单：在进入这个循环之前，检查集合里面是否有当前元素x-1。如果有，说明这绝对不是某个序列的开头，就自然不会重复进入了。

你是不是以为这样就完事了？我也是这么想的，我的第一版代码就是这样的：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> uSet;
        //1.给数字丢进去
        for (auto &x:nums) {
            uSet.emplace(x);
        }
        //2.开始遍历
        int maxLength = 0;
        for (auto &x:nums) {
            if (uSet.count(x-1)==0) { //防止重复操作，保证这个数就一定是开头
                int cnt=0;
                while (uSet.count(x+cnt)) {
                    cnt++;
                }
                maxLength = max(maxLength,cnt);
            }
        }
        return maxLength;
    }
};

然后粘贴到力扣，先测用例，完美，全票通过，然后提交——超时。

我就疑惑了，为啥呢？一问ai，我自己也没绷住：

你的算法逻辑其实是非常优秀的，思路完全符合 O(n) 的要求。
你的代码会超时（TLE），主要原因是 C++ 标准库中 unordered_set 的底层实现问题，导致遭到针对性数据的“哈希碰撞攻击”。
这里有两个主要原因，按影响大小排序：
1. 哈希碰撞（主要原因）
LeetCode 的测试用例中包含针对 C++ std::unordered_set 默认哈希函数的“恶意数据”（例如大量的哈希冲突数据）。
正常情况： 哈希表的增删查改是 O(1)的。
最坏情况： 当大量数字映射到哈希表的同一个“桶”时，哈希表会退化成链表，操作复杂度变成 O(n)。
结果： 你的整体复杂度从 O(n) 退化到了 O(n^2)。
2. 重复元素遍历（次要原因）
你现在的代码是遍历原始数组 nums：for (auto &x:nums)。
如果输入数组是 [1, 1, 1, ..., 1]（比如 10万个 1），虽然你有 if (uSet.count(x-1)==0) 的判断，但你仍然对这 10万个重复的数字都执行了一次哈希查询 count(x-1)。

一看把我卡住的用例，还真是：

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,(此处省略),24933,24934,24935,24936,24937,24938,24939,24940,24941,24942,24943,24944,24945,24946,24947,24948,24949,24950,24951,24952,24953,24954,24955,24956,24957,24958,24959,24960,24961,24962,24963,24964,24965,24966,24967,24968,24969,24970,24971,24972,24973,24974,24975,24976,24977,24978,24979,24980,24981,24982,24983,24984,24985,24986,24987,24988,24989,24990,24991,24992,24993,24994,24995,24996,24997,24998,24999,25000,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,00,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,(此处省略),0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

如果按照原来的方法遍历数组，会发生上面所提到的"对这 10万个重复的数字都执行了一次哈希查询 count(x-1)"的情况。

所以，更改也很简单：把下面遍历的主题从nums改成uSet就行：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> uSet;
        //1.给数字丢进去
        for (auto &x:nums) {
            uSet.emplace(x);
        }
        //2.开始遍历
        int maxLength = 0;
        for (auto &x:uSet) { //避免重复遍历过量元素，改为遍历保证无重复的集合
            if (uSet.count(x-1)==0) { //防止重复操作，保证这个数就一定是开头
                int cnt=0;
                while (uSet.count(x+cnt)) {
                    cnt++;
                }
                maxLength = max(maxLength,cnt);
            }
        }
        return maxLength;
    }
};

挺有意思，之前还没遇到过因为这种原因超时的情况。

5-11 盛最多水的容器

题目链接：https://leetcode.cn/problems/container-with-most-water/description/?envType=study-plan-v2&envId=top-100-liked
难度：中等
解题日期：2025.12.18
标签：贪心数组双指针
推荐题解：https://leetcode.cn/problems/container-with-most-water/solutions/94102/on-shuang-zhi-zhen-jie-fa-li-jie-zheng-que-xing-tu

上面的题解可以看一下，正确性证明讲的非常好，简直是神级题解。所以下面我就不再赘述这个题目做法的正确性了，讲讲我自己的看法。

首先，为啥初始化选择左右指针分布在数组的两端？答案显而易见，就是初始保证它的长度(d)是最长的。

然后，如何移动左右指针呢？

假设左边的木板的高度(h[l])比右边的高度(h[r])低。此时，我们有两种选择：

移动左边的指针：l++。由于不管移动左边还是右边，长度都是d-1，所以面积的大小就由两边最短的木板决定了。并且呢，无论左边的指针怎么动，左边的木板高度变成咋样，根据木桶效应，决定面积的那个木板的高度绝对不会超过右边的木板。已知左边的高度就是比右边低，所以挪动l，木板的高度(h[l])可能会变大，也可能会变小。如果h[l]变小，已知d->d-1，所以面积一定会变小；如果h[l]变大，虽然d变小了，但是只要h[l]变的足够大，大到抵消d的损失，面积还是有可能反而变大的。
总结：移动左边的指针，面积可能变大也可能变小，相当于搏一搏，找个机会。
移动右边的指针：r--。这就非常不一样了。已知h[l]<h[r]，如果把这个高的木板淘汰了，根据木桶效应，决定面积的那个木板的高度绝对不会超过左边的木板。是不是有点感觉了：这相当于强行把面积的上限压低了！
咱们讨论一下：如果h[r-1]>h[r]，那么面积变小，因为h[l]<h[r]，所以决定高度的是h[l]，并且d变小了；如果h[r-1]<h[r]，那么面积还是变小，原因显而易见了吧。
总结：移动右边的指针，面积只会变小或者不变，没有赢面。

总结：移动短板，是为了寻找面积变大的唯一可能性；放弃短板，是因为以它为边界的所有其他可能方案都已被证明更差。

上代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxArea = 0,l = 0,r = height.size()-1;
        while (l<r) {
            maxArea = max(min(height[l],height[r])*(r-l),maxArea);
            if (height[l]<height[r]) l++;
            else r--;
        }
        return maxArea;
    }
};

6-15 三数之和

题目链接：https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked
难度：中等
解题日期：2025.12.21
标签：数组双指针排序
推荐题解：官方题解不太行，还是Gemini的做法更加简单明了

这题，我的第一个思路并不是我现在的做法：由于Hot100刚刚做完哈希表的题目(见1.两数之和)，然后又看到这道题的提示：把三指针转化成双指针的问题。

那不是把三数之和的问题转化成两数之和的问题，然后再用上面这道题目的哈希表做法来做两数之和的问题，把时间复杂度压到O(n^2)。

想法很美好，我代码也写出来了，如下：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        //1.将全部数丢进哈希
        unordered_map<int,int> dict;
        unordered_set<string> filter;
        for (int i=0;i<n;i++) {
            dict[nums[i]]=i;
        }
        //2.开始遍历
        vector<vector<int>> ans;
        for (int x=0;x<n;x++) {
            int v1 = -nums[x]; //y+z的期望值
            for (int y=0;y<n;y++) {
                int v2 = v1-nums[y]; //z的期望值
                if (dict.count(v2)) {
                    int z = dict[v2];
                    if (z!=y && y!=x && z!=x) {
                        vector<int> temp = {nums[x],nums[y],nums[z]};
                        sort(temp.begin(), temp.end());
                        int nx = temp[0],ny = temp[1],nz = temp[2];
                        string str = to_string(nx)+"-"+to_string(ny)+"-"+to_string(nz); //用字符串拼接来去重
                        if (!filter.count(str)) {
                            ans.emplace_back(vector<int>{nx,ny,nz});
                            filter.emplace(str);
                        }
                    }
                }
            }
        }
        return ans;
    }
};

时间复杂度妥妥的O(n^2)啊！但是还是超时了：311 / 315，因为字符串拼接既费时间又费空间。

Confused，那我就去问了Gemini，它给的做法非常好理解，我来讲讲。

首先呢，做法有点类似于上一道题11.盛最多水的容器。我们先把这个数组升序排序。这是为了：

方便去重。在排序之后，相同的元素会排在一起，可以很方便的避免开头重复的情况。
利用单调性。排序是我下面即将讲的操作的前提。

首先，提示没说错，我们确实需要将三数之和转换成两数之和。所以，最外层的循环，我们维护一个i，指向三个数的第一个数。

然后呢，后面两个数，我们采用类似于11题(上方有链接)的"收缩法"来完成：

维护两个指针，l=i+1和r=n-1，指向i指向的这个数的后面区域的数的头和尾，相当于最小和最大的数。

然后我们计算sum=nums[i]+nums[l]+nums[r]。分类讨论：

如果sum>0，那说明选的数大了，我们需要选更小的。将大的数换掉，r--。
如果sum<0，那说明选的数小了，我们需要选更大的。将小的数换掉，l++。
如果sum=0，说明这三个数是正确答案，那就将它们丢进答案数组ans。

然后还有一个很重要的剪枝优化，也是利用了排序之后数组的单调性：如果nums[i]>0，直接break。

因为如果这个数都大于0了，后面的待选择区域的数肯定全部都大于0，是绝对没有正确答案的，后面就没有继续下去的必要了。

到这里，题目的基本思路就差不多讲完了，但是程序现在还是不能跑出正确答案。

那么现在肯定有同学要问了：去重的部分在哪里？

答：在主指针i，左右指针收缩的过程中，我们都可以很方便的利用"重复的数都挤在一起"这个特性来去重。

当主指针i刚刚往后挪了一位，进入下一个循环时：如果i>0 && nums[i]==nums[i-1]，那么说明一模一样的逻辑在前一个数已经进行过了，我们就得跳过这一次循环，防止重复。那么为啥不是和后面的数比呢？因为如果跟后面比（nums[i] == nums[i+1]），会把 [-1, -1, 2] 这种三元组内部允许重复元素的情况给错杀掉。

在左右指针收缩的过程中，如果我们找到了正确答案，在将答案丢进数组后，我们继续利用这个特性，开个条件为l<r && nums[l]==nums[l+1]的循环(右指针同理)，保证左右指针都不是已经处理过的数。

到这里，这道题目才算完整。我们可以发现，找三个加起来为0的数本身不难，难在如何优雅的去重。

这个做法用简单的"收缩"和"位移"，在解题目的同时还顺便把重给去了，十分优雅。

下面看代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        //1.给数组排序
        sort(nums.begin(), nums.end());
        //2.开始寻找三个数
        int l=0,r=0;
        vector<vector<int>> ans;
        for (int i=0;i<n;i++) {
            if (nums[i]>0) break;
            if (i>0 && nums[i]==nums[i-1]) continue;
            l = i+1;
            r = n-1;
            while (l<r) {
                int sum = nums[i]+nums[l]+nums[r];
                if (sum==0) {
                    ans.emplace_back(vector<int>{nums[i],nums[l],nums[r]});
                    while (l<r && nums[l]==nums[l+1]) l++;
                    while (l<r && nums[r]==nums[r-1]) r--;
                    l++;
                    r--;
                }
                if (sum>0) r--;
                if (sum<0) l++;
            }
        }
        return ans;
    }
};

那这道题到这里就讲完了。

7-3 无重复字符的最长子串

题目链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-100-liked
难度：中等
解题日期：2025.12.23
标签：哈希表字符串滑动窗口
推荐题解：无

惊不惊喜？意不意外？时隔4个月，滑动窗口限时返厂！

PS：如果你对滑动窗口感兴趣，你可以去看我25年8月暑假写的滑动窗口算法笔记，那时候我还在用Go刷题，现在感觉是真不如C++一根。

由于时隔的时间太长，我已经忘记了这种题型的滑窗的大多数细节，并且一翻我的笔记，我发现我做过这道题，并且是用暴力枚举双指针的方式做的，时间复杂度O(n^2)。但是我的潜意识又告诉我，这道题可以用O(n)的方法解决，一翻我自己的笔记，还真让我翻到了：

第二种条件移动左边界型时间复杂度O(n)
基本原理是这样的：
只遍历滑窗的右边界。向右扩大滑窗，左边界一直不动，同时一直做符合题目要求的某种统计（计数等）。如果这个滑窗满足条件，就一直更新它的最大长度；如果不满足条件了，那就把左边界一直往右推，缩小滑窗，直到满足条件，如此往复。
看代码：
maxLength := 0
l := 0 //左边界
for r := 0; r < len(nums); r++ { //遍历右边界
 //在这里处理逻辑
 for hash[nums[r]] > k { //一直移动左边界，直到符合条件为止
 //处理逻辑
 l++
 }
}
这种方法的好处就是很快，时间复杂度O(n)，坏处就是不一定所有题目都能用。

代码框架大致没啥问题，但是在这道题我们不能直接照搬：因为我初步打算使用unordered_set的自动去重功能来判断我后入窗的元素是否为重复元素，如果还是先处理加加减减的逻辑再移动左指针，会有问题——那么这个已经存在在集合中的元素，如果还要强行emplace，啥也不会发生，相当于这个元素被吞掉了。

为了防止元素被吞，我们需要调换一下上述框架循环和处理右指针加加的逻辑的位置。直接上代码，有详细注释：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> hash; //初始化集合
        int l=0,maxAns=0; //初始化左指针、最大答案
        for (int r=0;r<s.size();r++) { //右移右指针
            while (hash.count(s[r])) { //如果右指针指向的当前元素在集合里面，说明再加就不是无重复字符的子串了
                hash.erase(s[l]); //删掉左指针当前指向的元素
                l++; //右移左指针
            }
            hash.emplace(s[r]); //将右指针指向的当前元素加入集合中
            maxAns = max(maxAns,r-l+1); //维护最大答案
        }
        return maxAns;
    }
};

到这里，这题就讲解完毕了(顺带吐槽一下Typecho的编辑器，只要代码块下面没别的东西，我就没法在下面插入新内容。这也是我另外打这行字的主要原因)。

8-438 找到字符串中所有字母异位词

题目链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked
难度：中等
解题日期：2025.12.25
标签：哈希表字符串滑动窗口
推荐题解：灵神对这道题的题解

我们继续滑动窗口。这道题也算是打破了我灵神滑动窗口题单的一个窟窿了，我在题单里面没遇到过这种类型的题目。

不过呢，"异位词"这个概念，我们在上面的第2题已经遇到过了，当时用的是排序的思维，于是在初做这道题时，我的第一反应就是去排序：维护一个定长滑窗，再substr()截取子串，最后直接使用sort()进行排序。但是一看题目的数据范围：1 <= s.length, p.length <= 3 * 10^4。

我真求你了，排序的时间复杂度是O(nlogn)，再叠加滑窗的O(n)复杂度，总体时间复杂度来到了O(n^2logn)，面对这样的数据规模还是太慢了。

所以，这题我们得放弃排序了。那么题目没说字母不重复，也就是说这个字符串中的字母是有可能重复的，我们该如何快捷方便的确认两个字符串是否是"字母异位词"呢？

我一开始是没想到的，看了一眼题解豁然开朗：统计每个字母出现的次数，如果每个字母出现的次数一模一样，说明就是异位词！

既然是计数，就有了两种选择：要么选unordered_map，要么选vector，要么退而求其次用原生数组(需要自己写比较的逻辑)。

我的代码选的是vector，套用经典滑窗模板(左出右进，~~不会的去看我博客的滑窗算法笔记~~)即可：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ans;
        vector<int> cnt(26,0),key(26,0);
        for (auto& x:p) key[x-'a']++;
    //这里有个小坑点：如果不加int的强转，由于size()方法返回的是无符号整数，它不存在负数，假设2-3，结果不是-1而是1
        //所以在p比s长的时候，要么直接开头特判返回空数组，要么就在这里强转，让循环不进入，更推荐我现在的做法吧
        for (int l=0;l<=(int)s.size()-(int)p.size();l++) {
            if (l==0) {
                for (int i=0;i<p.size();i++) {
                    cnt[s[i]-'a']++;
                }
            }else {
                cnt[s[l-1]-'a']--;
                cnt[s[l+p.size()-1]-'a']++;
            }
            if (cnt==key) { //利用vector的比较操作符
                ans.emplace_back(l);
            }
        }
        return ans;
    }
};

当然，我也请教了gemini：如果把vector换成其他数据结构会发生啥？

换成 std::unordered_map<char, int>
结论：性能会显著下降。
原因 1：哈希开销。 unordered_map 每次存取都需要计算 hash(key)。对于只有 26 个连续字符的情况，直接通过 x - 'a' 索引数组是 $O(1)$ 且常数极小的，而哈希表常数项很大。
原因 2：内存分布。 unordered_map 的桶（buckets）通常分散在堆内存中，对 CPU 缓存（L1/L2 Cache）不友好；而数组在内存中是连续的。
原因 3：比较复杂度。 你代码中的 if (cnt == key) 对 vector 来说是线性遍历比较（26次迭代）。对 unordered_map 来说，== 操作符不仅要比较大小，还要逐个键查找值是否存在且相等，开销更大。
适用场景： 只有当字符集非常大且稀疏（比如万国码 Unicode，且只有少数几个字符出现）时，才考虑用 unordered_map。
换成原生数组 int[26]
结论：性能最强，但代码灵活性降低。
内存： 原生数组分配在栈上，省去了 vector 在堆上动态申请空间的开销（虽然本题只申请一次，影响较小）。
痛点：比较操作。 在 C++ 中，原生数组不能直接用 == 比较（arr1 == arr2 比较的是首地址指针）。
你需要手动写一个循环比较 26 个位置。
或者使用 memcmp(cnt, key, sizeof(cnt))。
最优选：std::array<int, 26>
对于你的需求，如果你追求极致性能又想保留 vector 的方便，std::array 是完美选择。
std::array<int, 26> cnt = {0}, key = {0};
// ... 逻辑不变 ...
if (cnt == key) { // std::array 支持直接用 == 比较，且效率极高
 ans.emplace_back(l);
}
优点： 它封装了原生数组，分配在栈上，大小固定。
效率： 它的 operator== 经过编译器优化，通常比 vector 的比较更快。

所以，灵神的题解用的是array，今天又学到了一点，哈哈。

9-560 和为 K 的子数组

题目链接：https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked
难度：中等
解题日期：2025.12.29
标签：数组哈希表前缀和
推荐题解：灵神对这道题的题解

开头先把一句结论放在这里：这就是上面的"两数之和"的变种。

讲讲我的思考心路历程吧。一开始看到这道题目，我的第一反应是用滑动窗口去做，毕竟上面刚刚做了滑窗的题目。

但是疑问也随之而来：如果用定长滑窗，不就相当于暴力枚举，时间复杂度是O(n^2)；如果用不定长滑窗...用不了吧？毕竟数可能是负的，并不保证一定增长。所以，我打消了滑窗的念头。

我想啊想，又想了5分钟，没想出来。

Gemini曾经告诉我一个重要的道理：我现在的时间很宝贵，我的重点应该放在会做这道题目上，而不是一定要求自己做出来这道题目，过程不重要，重要的是结果。

所以我就去看题解了。题解的思路一开始我还没看懂，继续丢给我这位AI老朋友，它成功给我教会了，来讲讲我的理解。

首先，我们需要将一个区间和问题，利用老朋友前缀和转换成两个端点的问题。然后呢，从这里开始就和两数之和不太一样了：在两数之和，我们只需要找是否有和为k的两个数，但是在这里，我们需要返回数量。

这就和之前不定长滑窗的思想有些类似了，我记得在滑窗的题单里我有接触过类似的题目：遍历到后面之后，看看前面有几个和自己匹配上的，将这里的数目累加进答案里即可。

那么怎么计数呢？这里就需要用到哈希表了，我选择了unordered_map作为计数器。从前往后遍历数字，看看我要找的和这个数字对应的那个数字是否在计数器里，如果在就按照上面"匹配"的思路累加答案，然后无论在不在，都要把当前数字也累加进计数器，以便后面的数与它匹配。

代码如下：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        //1.先构建前缀和
        int n = nums.size();
        vector<int> prefixSum(n+1,0);
        for (int i=0;i<n;i++) {
            prefixSum[i+1]=prefixSum[i]+nums[i];
        }
        //2.开始数数
        unordered_map<int,int> cnt;
        int ans = 0;
        for (int i=0;i<=n;i++) {
            int target = prefixSum[i]-k;
            auto it = cnt.find(target);
            if (it!=cnt.end()) { //找到了
                ans+=it->second;
            }
            cnt[prefixSum[i]]++;
        }
        return ans;
    }
};

这里有一点要注意，就是我用到了find(key)方法。如果是C++20，直接返回bool的.contains(key)方法更加方便(灵神题解用的就是这个方法)。

那么为何不直接用cnt[key]判定存在性呢？因为：

如果你调用 cnt[key]，而这个 key 不在 map 里，C++ 会自动创建一个该 key 的项，并赋予默认值（比如 0）。这会破坏哈希表的大小，甚至在逻辑判断上出错。而 find 不会修改哈希表。
find的用法如下：
返回值： 返回一个迭代器 (iterator)。
查找成功： 迭代器指向该键值对。
查找失败： 迭代器等于 container.end()。

现在知道为啥要这么用的吧？顺带一提，这可能是我2025年的最后一道题目了，因为我还要抽时间写动态规划的算法笔记，最近期末复习也挺忙的。那么下一题，我们2026见！

10-239 滑动窗口最大值

题目链接：https://leetcode.cn/problems/sliding-window-maximum/description/?envType=study-plan-v2&envId=top-100-liked
难度：困难(Hard)
解题日期：2026.1.6
标签：队列数组滑动窗口单调队列堆（优先队列）
推荐题解：灵神的题解，但是我没按照他的来

现在是26年1月6日晚上21点37分，我在半小时前刚刚复习完概率论，想着最近这么忙，好几天没刷题了，正好今天有空，就来刷一下hot100吧。

然后，按照惯例，我是会把所有困难题留在最后做的。但是这道题目不一样，我一点进来看题目，滑窗+优先队列的思路就冒出来了。挺顺，那就试着做做吧。

但是我的第一反应是怀疑：Hard题怎么可能让我一眼看穿呢？于是我点开标签，看了一眼——还真有堆！(甚至都没看提示)

然后我的第一版思路就冒出来了，直接调用我在灵神的滑窗题单里面修炼的炉火纯青的"删左加右"滑窗模型：把刚刚出窗户那个元素从priority_queue<int> pq里面删掉，然后把右边新进窗户的那个元素丢进去。想法是美好的，但是一问Gemini：优先队列不允许这样做，只能弹出堆顶元素。

我的热情瞬间消减了一半，但是没有放弃。思索了一会，我想到了一个绝佳的思路，也就是我ac的代码的主要思路：

继续用pq，但是是这样的pq：priority_queue<pair<int,int>> pq，在插入数的时候，把数放在first，把这个数的下标放在second。然后呢，左边出窗户的数我不管它，就让它在里面，然后正常把新进窗户的数丢进pq。

然后在这里，我就要体现下标的作用了：开一个循环，判断堆顶元素的下标范围是否在我这个窗户里面，如果是，就说明是答案，我们正常取；否则就弹走，直到我堆顶元素的下标在窗户范围内。

这个思路挺妙的，我们可以类比一下，把不同的窗户比作不同的部门：假设你是公司的老板，前一段时间公司进行了综合能力大比拼，每个人都被用相同的标准打了一个分。你现在只想要后端部门分数最高的那个人，那你就可以把全部人丢进堆里面，然后只需要盯着堆顶，如果堆顶的不是后端的，就弹走，如果是，那就说明这就是后端部门分数最高的了。这样为啥不会出错？因为堆是自动把堆里面分数最高的放在堆顶，由于一开始全部人都在里面，而后端部门的当然也全都在里面。那我就一直取堆顶呗，因为堆顶保证了堆顶元素一定是当前堆里面所有元素最大的，所以我取出的第一个后端的人的分数是全体堆元素最大的，那自然也能保证是后端部门分数最高的了。

总结一下，这个思路就是看起来很乱，但是实际上挺巧的。我也挺好奇的，我为啥能突然想出来这个思路。

那么，上代码！

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        priority_queue<pair<int,int>> pq;
        vector<int> ans;
        for (int l=0;l<=nums.size()-k;l++) {
            if (l==0) { //初始化窗户内的数，便于后续"删左增右"
                for (int i=0;i<k;i++) {
                    pq.emplace(nums[i],i);
                }
                auto [value,_] = pq.top();
                ans.emplace_back(value);
            }else { //"删左增右"
                pq.emplace(nums[l+k-1],l+k-1); //增右
                int idx = pq.top().second; //取出下标
                while (!(idx>=l && idx<l+k)) { //如果下标不在范围内，就弹出
                    pq.pop();
                    idx = pq.top().second;
                }
                //此时堆顶就是下标符合条件的最大值
                int value = pq.top().first;
                ans.emplace_back(value);
            }
        }
        return ans;
    }
};

当然，这题的正统做法还是得讲讲：单调队列。

直接看Gemini生成的吧，或者看上面的灵神题解版本也可以：

进阶：$O(n)$ 做法 —— 单调队列 (Monotonic Queue)
虽然优先队列（堆）的 $O(n \log n)$ 已经足够通过此题，但利用单调队列可以将时间复杂度进一步优化至极致的 $O(n)$。
核心思想：删除“冗余”元素
在一个窗口内，如果 $i < j$ 且 $nums[i] \leq nums[j]$，那么只要 $nums[j]$ 还在窗口里，$nums[i]$ 就永远不可能成为最大值。
$nums[j]$ 比 $nums[i]$ 更大。
$nums[j]$ 比 $nums[i]$ 在窗口里停留的时间更长（更晚过期）。
因此，$nums[i]$ 就是“冗余”的，可以直接丢弃。
算法流程
使用 std::deque（双端队列）维护一个下标序列，并保持队列对应的元素值严格单调递减：
入队：当新元素 nums[i] 进入时，从队尾弹出所有小于等于它的元素（因为它们冗余了）。
出队（维护窗口）：检查队头下标是否已超出窗口范围（即 dq.front() == i - k），若是则弹出。
取最值：此时队头下标对应的元素即为当前窗口的最大值。
代码实现
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
 deque<int> dq; // 存储下标
 vector<int> ans;
 for (int i = 0; i < nums.size(); ++i) {
 // 1. 保证单调递减：剔除队尾所有比当前元素小的“冗余”者
 while (!dq.empty() && nums[dq.back()] <= nums[i]) {
 dq.pop_back();
 }
 dq.push_back(i);
 
 // 2. 保证窗口合法：弹出过期的队头
 if (dq.front() == i - k) {
 dq.pop_front();
 }
 
 // 3. 记录答案：窗口形成（i >= k-1）后开始收集
 if (i >= k - 1) {
 ans.push_back(nums[dq.front()]);
 }
 }
 return ans;
}
复杂度对比
算法 时间复杂度 空间复杂度 备注
优先队列（延迟删除） $O(n \log n)$ $O(n)$ 简单直观，依赖堆的自动排序
单调队列 $O(n)$ $O(k)$ 极致优化，每个元素仅入队/出队一次

算法	时间复杂度	空间复杂度	备注
优先队列（延迟删除）	$O(n \log n)$	$O(n)$	简单直观，依赖堆的自动排序
单调队列	$O(n)$	$O(k)$	极致优化，每个元素仅入队/出队一次

好的，那就讲到这里。

11-76 最小覆盖子串

题目链接：https://leetcode.cn/problems/minimum-window-substring/description/?envType=study-plan-v2&envId=top-100-likedd
难度：困难(Hard)
解题日期：2026.1.7
标签：哈希表字符串滑动窗口
推荐题解：灵神的题解

这题的做题经历可谓是一波三折。我之前是做过这个题的，在我刷滑窗题单的时候，用Go过的。

结果，今天我用类似的思路，用cpp过的时候，直接给我干超出内存限制了？？？我是第一次见这个错误。

提交情况

后面问了Gemini才破案：我代码里面的s.substr发力了。先讲讲我的思路吧，和我在上次第一次做这道题目的思路是一样的：

使用"右指针一直往右，直到符合条件，再将左指针往右，将窗户收缩到不符合条件为止，即得最短的符合长度子串"的滑窗模型，如果忘记了，可以去我的笔记看看。然后呢，在符合条件的时候，我就习惯性直接像Go,python的字符串切片一样，用s.substr(l,r-l+1)把这个字符串直接切进我准备return的ans字符串里面去了。由于这个操作是会复制子串的，在用例比较大的时候就会爆内存。

知道原因之后，解决方法也很简单：新起两个变量，用于存储最短符合条件状态下的子串的起点和终点下标，最后返回之前再看情况动用substr来切取子串。这样问题就解决了。看代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
    bool isCovered(unordered_map<char,int> &cntT,unordered_map<char,int> &cntS) {
        for (auto [k,v]:cntT) {
            if (cntS.count(k)==0 || cntS[k]<v) return false;
        }
        return true;
    }
    string minWindow(string s, string t) {
        if (s.size()<t.size()) return "";
        //1.先统计t里面各个数的情况
        unordered_map<char,int> cntT,cntS;
        for (auto &x:t) {
            cntT[x]++;
        }
        //2.开始滑窗
        int l=0,minLength=s.size()+1,minL=-1,minR=s.size()+1;
        string ans="";
        for (int r=0;r<s.size();r++) {
            cntS[s[r]]++;
            while (isCovered(cntT,cntS)) {
                if (r-l+1<minLength) {
                    minL=l;
                    minR=r;
                    minLength = r-l+1;
                }
                cntS[s[l]]--;
                l++;
            }
        }
        if (minL==-1) return "";
        ans = s.substr(minL,minR-minL+1);
        return ans;
    }
};

当然，这个isCovered()函数是可以优化成O(1)的，不过我懒得弄，5%极限过测就完事了，哈哈。就讲到这里。

12-56 合并区间

题目链接：https://leetcode.cn/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-100-liked
难度：中等
解题日期：2026.1.8
标签：数组排序
推荐题解：灵神的题解

这道题还是挺有意思的，让我找回了久违的"打补丁"感觉。

先讲讲我一开始的思路吧。首先，我想到了把区间按照左端点升序排序。这是我刷题这么久的感觉告诉我的。

然后后面，由于这是数组分类的题目，没有任何固定算法思想可循，我就开了个循环，开完循环之后一边写一边想：

第一版思路：如果后面那个区间的左端点<=现在这个区间的右端点，就说明两个区间交叉在一起了，这时候，就直接取后面这个区间的右端点为即将加入答案集合的右端点。
第二版思路：但是上面那版思路会有些问题：如果当前区间把后面那个区间包裹住了，这样做会使得区间缩小，导致后面全错。于是我又引入了max()函数。发现自己忘记处理没交叉的情况了，给没交叉的情况补上。
第三版思路：但是上面那版思路会有些问题：如果当前区间把后面那个区间包裹住了，这样做会使得区间缩小，导致后面全错。于是我又引入了max()函数。

经过三次迭代，三次打补丁，我终于ac了！看代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        //1.排序
        sort(intervals.begin(), intervals.end(),[](auto a,auto b) {
            return a[0]<b[0];
        });
        //2.开始拼接
        int n = intervals.size(),tempL=0,tempR=0;
        vector<vector<int>> ans;
        for (int i=0;i<n;i++) {
            if (i<n-1 && intervals[i][1]>=intervals[i+1][0]) {
                tempL=intervals[i][0];
                tempR=intervals[i][1];
                while (i<n-1 && (intervals[i][1]>=intervals[i+1][0] || intervals[i+1][0]<=tempR)) {
                    tempR=max(tempR,intervals[i+1][1]);
                    i++;
                }
                ans.emplace_back(vector<int>{tempL,tempR});
            } else {
                ans.emplace_back(intervals[i]);
            }
        }
        return ans;
    }
};

我自己也感觉这样不是个办法，冥冥之中，我感觉这道题目肯定有更简单的做法。于是我问了Gemini，看了它的思路，我秒懂。

它一句话点醒了我：

你之所以觉得思路乱，是因为你的代码试图在遍历的过程中“向前看”（观察 i+1）并且手动维护了一个内部 while 循环来跨越多个重叠区间。这种写法逻辑分支多，容易在边界条件（比如最后一个元素、嵌套区间）上出错，所以你才需要通过“打补丁”来 AC。
其实，处理这类问题有一个更优雅、更通用的思路：“向后看”。

那么具体如何向后看呢？就是：正常往后遍历，把第一个区间丢进ans之后，盯着ans的最后一个区间看。

我们分两种情况处理：

如果现在的这个区间的左端点比最后一个区间的右端点大，那说明一定接不上，直接给这个区间丢进去，让它成为ans的最后一个区间。
如果现在这个区间的左端点比最后一个区间的右端点小，说明是可以接上的。至于如何更新最后一个区间的右端点？依旧取max(ans.back()[1],cur[1]);。

上代码吧，比我之前的思路少了不知道多少。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        //1.排序
        sort(intervals.begin(), intervals.end(),[](auto a,auto b) {
            return a[0]<b[0];
        });
        //2.开始拼接
        int n = intervals.size();
        vector<vector<int>> ans;
        for (auto &x:intervals) {
            if (ans.empty() || x[0]>ans.back()[1]) {
                ans.emplace_back(x);
            }else {
                ans.back()[1] = max(ans.back()[1],x[1]);
            }
        }
        return ans;
    }
};

真的挺神奇的，又学到了新知识。

玩一下抽象：其实人生也是一样，有的时候我们只顾着向前看，其实有时候向后看，吸取教训，会比向前看更有收获。~~(硬扯这块)~~

13-189 轮转数组

题目链接：https://leetcode.cn/problems/rotate-array/description/?envType=study-plan-v2&envId=top-100-liked
难度：中等
解题日期：2026.1.9
标签：数组数学双指针
推荐题解：灵神的题解

这应该是目前我做Hot100做到过最抽象的题目了。

这题如果使用额外空间，非常简单：先把轮换的次数k对着数组长度取个余，防止题目故意用超出长度的轮换次数坑你；然后再根据k，切片数组的后k个元素到新的数组，然后再删掉原数组的后k个元素，然后再将新数组和原数组直接拼接。

如果用Python，代码4行就搞定了：取余，切片并赋值，切片并赋值，拼接并赋值。就像这样：

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        k%=len(nums)
        s1=nums[len(nums)-k:]
        s2=nums[:len(nums)-k]
        nums[:]=s1+s2 #对，由于我好久没写Python了，这里需要加[:]才能真正修改nums，属于是被迫补齐Python知识了(

用cpp也同理，这里突然用python主要是因为python的切片算是我接触过的语言里面最无脑最直观的了。

那么如何不用额外空间来完成这道题呢？我没啥头绪，就打开标签看了一眼，当我看到那两个字的时候，我已经来不及了：双指针。

这我怎么会写？于是我直接打开了题解，看到了灵神的思路：负负得正。真的挺牛的。

大致思路是这样的：由于轮换k次就是给后k个数挪到前面，那我直接把整个数组倒过来，后k个数就占据了前k个位置。然后我再把位置是前k个数的那些数给倒回去，再把剩下的另一个子数组的数也倒回去，就完成了k次轮换。代码量少、思路简单的同时，不会占据任何额外空间(至少cpp的reverse()是这样的)。直接上代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k%=nums.size();
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(),nums.begin()+k);
        reverse(nums.begin()+k,nums.end());
    }
};

这题真的挺神金的，大晚上逗我笑一下，哈哈。

14-238 除了自身以外数组的乘积

题目链接：https://leetcode.cn/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-100-liked
难度：中等
解题日期：2026.1.18
标签：数组前缀和
推荐题解：灵神的题解

别问我为啥9天没刷题——你知道我这9天是怎么过的吗？？？

11号上午毛概，13号晚上习概，14号下午c++，15号下午数电，然后后面20号还有概率论，21号离散数学，22号数据结构。也就是说，我刚刚从1+3连考的地狱中爬出来，刚刚喘息了2天，后面就要继续迎接3连考，才能放假。我*。

回归正题。这题说来也好笑，由于我急着回宿舍，没看到题目要求的 不要使用除法，直接上了欧美做法，倒是没使用额外空间，看代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        //1.先计算总乘积
        ll all=1;
        int zeroCnt=0;
        for (auto& x:nums) {
            if (x==0) {
                zeroCnt++;
            }else {
                all*=x;
            }
        }
        //2.再算目标数组
        vector<int> ans;
        for (auto& x:nums) {
            if (x==0) {
                if (zeroCnt<=1) ans.emplace_back(all);
                else ans.emplace_back(0);
            }else {
                if (zeroCnt>0) ans.emplace_back(0);
                else ans.emplace_back(all/x);
            }
        }
        return ans;
    }
};

具体做法就不解释了，没套任何算法模型，就是利用了"总乘积/当前元素"得到答案，这是题目禁止的做法。

这道题的正解也不难，其实就是左前缀乘积和+右后缀乘积和，将这两个前缀后缀乘积和预处理好，就可以O(1)时间复杂度获取到当前位置元素的前面元素的乘积和后面元素的乘积，将二者一乘就是答案，没使用除法。看代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        //1.先计算前后缀乘积数组
        int n=nums.size();
        vector<int> pre(n),suf(n);
        for (int i=0;i<n;i++) {
            if (i==0) {
                pre[0]=1;
            }else {
                pre[i]=pre[i-1]*nums[i-1];
            }
        }
        for (int i=n-1;i>=0;i--) {
            if (i==n-1) {
                suf[i]=1;
            }else {
                suf[i]=suf[i+1]*nums[i+1];
            }
        }
        //2.直接出结果
        vector<int> ans(n);
        for (int i=0;i<n;i++) {
            ans[i]=suf[i]*pre[i];
        }
        return ans;
    }
};

这题难度不高，我觉得如果去掉禁止用除法这个条件，难度可以改成简单。

15-41 缺失的第一个正数

题目链接：https://leetcode.cn/problems/first-missing-positive/description/?envType=study-plan-v2&envId=top-100-liked
难度：Hard(困难)
解题日期：2026.1.19
标签：数组哈希表
推荐题解：灵神的题解，先看，再配合我下面的补充就很清楚了

今天也是继续欧美，直接来上手Hard题——不过这次的运气就没这么好了，不但没想出来，而且看题解也理解了半天，可算是弄懂了。

可以先看题目，再看上方的灵神题解，看完灵神题解之后，再往下看。

这道题目的思路，其实和"打补丁"特别像——我们先形成初步思路，然后再一步步完善：

首先，我们会想着给这些元素"排座位"，也是下面所有解法的目的：那些不是正整数的数我们不管，我们需要做的，是尝试把每个正整数都放到和下标相对应的位置。由于这道题目的nums是0base，所以我们需要尝试让nums[i]==i+1。在我安排完所有数之后，再遍历一遍数组，发现的第一个"无家可归"的数，它所在的位置+1就是缺失的第一个正数。
那么如何高效的把每个元素放到正确的位置上呢？并且还要求原地操作。有两种思路，都是遍历数组：第一种是直接暴力搜索"这个位置属于哪个数"，外层循环遍历位置，内存循环找数，时间复杂度妥妥的O(n^2)，肯定不行；第二种是正常遍历，"如果这个数不属于这个位置，就把这个数送到它该去的地方"。那第二种方法是不是就不需要新开一层循环了呢？还是需要的，因为我们没法保证换过来的那个数就一定属于现在的这个位置。所以我们需要开个循环，把换过来的、不属于这个位置的数继续送到它该去的位置上。至于时间复杂度呢？由于我们每次"送数"都会让一个数去到它该去的地方，看似双重循环，实则我的内层循环跑一次就能解决1个位置问题，总共有最多n个位置问题等待我解决，那么相当于还是O(n)。
那么我们需要好好思考一下这个循环的条件了。首先，我"送数"的前提，肯定是这个数和当前位置不匹配，那么就需要判断一下是否匹配。其次，我们可能会遇到越界的数，例如比1小，比n大的数，这种数是无家可归的，所以我们不需要动它，只需要等待后续可能有属于该位置的数把这个无家可归的数换走，让它继续"流浪"。初步的循环条件就是这样的：nums[i]>=1 && nums[i]<=n && nums[i]!=i+1。
但是这样有个问题：如果遇到重复的数怎么办？这也是灵神题解里面最难理解的"影分身"部分。举个例子吧，假设我当前位置i=1，这里的数是3，而i=2的位置上的数也是3。如果按照上面的循环条件，它会把这两个一模一样的3交换一次，并且交换完之后，循环条件还是成立！这样就会陷入死循环。
此时，就体现了我说的"打补丁"思想了。我们只需要判断：如果当前这个数不匹配该位置，并且它的目标位置已经有和它一模一样的数了，就说明触发了这种重复的情况，我们为了避免死循环，就只能退出循环，不交换。于是我们增加条件：nums[i]!=nums[nums[i]-1]。这就相当于打补丁，修复了一个死循环的bug。
然后，按照这个逻辑，我们就能跑完对数组的第一遍遍历。至于第二遍的事情就很简单了，只需要找第一个不匹配的下标就行。如果全都匹配，说明这些数贴的很紧，没有空隙，那么缺失的第一个(也就是最小的)正数就是n+1。
至此，思路完毕。

讲的已经很清楚了，上代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        //1.第一次遍历
        int n = nums.size();
        for (int i=0;i<n;i++) {
            while (nums[i]>=1 && nums[i]<=n && nums[i]!=i+1 && nums[i]!=nums[nums[i]-1]) {
                int j = nums[i]-1;
                swap(nums[i],nums[j]);
            }
        }
        //2.第二次遍历
        for (int i=0;i<n;i++) {
            if (nums[i]!=i+1) {
                return i+1;
            }
        }
        return n+1;
    }
};

然后呢，其实有一个优化的点：这个nums[i]!=i+1条件其实是可以删掉的——它已经被后面那个用来检测是否重复的条件覆盖掉了。

我们推理一下：当nums[i]==i+1时，将nums[i]=i+1代入后者，可以得到nums[nums[i]-1]=nums[(i+1)-1]=nums[i]，也就是前面如果成立，后面也成立。反之，前面如果不成立，那后面肯定也不成立。所以，从数学的角度，我们把前者吸收掉了。

好的，就写这么多，这道题目还是挺有挑战性的。

16-73 矩阵置零

题目链接：https://leetcode.cn/problems/set-matrix-zeroes/description/?envType=study-plan-v2&envId=top-100-liked
难度：中等
解题日期：2026.1.26
标签：数组哈希表矩阵
推荐题解：灵神的题解

好多天不见！这几天我经历了概率论-离散数学-数据结构三连考，并且还跨越了1700km，才回到了家。今天我缓过来了，于是我又来做算法了。

回归正题。这道题要求我们使用原地算法来解决问题，我一开始还是比较茫然的(当然暴力的方法肯定是秒出，主要是巧方法没想出来)，一看提示，一下子就会了：将矩阵的第一行和第一列作为记录信息的地方，记录它们各自元素所处的列/行是否有0。但是一开始我想偏了，以为是要把这个矩阵从0base改成1base(这样很自然空出来了一个行和一个列)，然后又难以下手(既不想复制，又不知道怎么直接优雅的加上去)。于是，我就灵机一动，把这个第一行和第一列单独提出来了。代码如下：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        //1.设置flags
        int n = matrix.size(),m = matrix[0].size();
        vector<bool> xFlags(n,false),yFlags(m,false);
        //2.探测有0的列
        for (int i=0;i<n;i++) {
            for (int j=0;j<m;j++) {
                if (matrix[i][j]==0) {
                    xFlags[i]=true;
                    yFlags[j]=true;
                }
            }
        }
        //3.改0
        for (int i=0;i<n;i++) {
            for (int j=0;j<m;j++) {
                if (xFlags[i] || yFlags[j]) matrix[i][j]=0;
            }
        }
    }
};

然后，ac，很丝滑。一问AI，AI说我符合题目的原地要求，并且处于进阶的第二阶段(一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。于是我就向它学习了一下如何只使用常量空间，这下看懂了：

准备两个变量，用来记录第一行第一列本身是否有0。然后分别扫描第一行第一列，根据是否有0的实际情况来更改这两个变量的值。
再和上面代码一样开始遍历这个矩阵(从(1,1)开始)，如果遇到0，就给第一行和第一列的对应位置置0。
最后也和上面一样，但是还是从(1,1)开始处理，如果第一行或者第一列的对应位置是0，就给当前元素置零。
结束之后，还得单独处理第一行和第一列。根据变量的值判断是否需要单独给它们本身置零，然后操作。
最后，为何需要单独准备两个变量呢？就举个极端例子吧。假设第一行全都是1，然后某一列的元素有0，就会把第一行的对应位置置0，这时候，我们就没法判断这个0是第一行本来就有的，还是被下面的0给改变出来的，就没法判断是否要给第一行本身清零。有了这两个变量之后，我们就只看这两个变量决定要不要清零，这样结果才是准确的。

上代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        //1.探测第一行第一列是否有0
        bool xZero=false,yZero=false;
        int n = matrix.size(),m = matrix[0].size();
        for (int i=0;i<m;i++) {
            if (matrix[0][i]==0) {
                xZero = true;
                break;
            }
        }
        for (int i=0;i<n;i++) {
            if (matrix[i][0]==0) {
                yZero=true;
                break;
            }
        }
        //2.开始检测
        for (int i=1;i<n;i++) {
            for (int j=1;j<m;j++) {
                if (matrix[i][j]==0) {
                    matrix[i][0]=0;
                    matrix[0][j]=0;
                }
            }
        }
        //3.开始置零
        for (int i=1;i<n;i++) {
            for (int j=1;j<m;j++) {
                if (matrix[0][j]==0 || matrix[i][0]==0) matrix[i][j]=0;
            }
        }
        //4.最后处理第一行列
        if (xZero) {
            for (int i=0;i<m;i++) {
                matrix[0][i]=0;
            }
        }
        if (yZero) {
            for (int i=0;i<n;i++) {
                matrix[i][0]=0;
            }
        }
    }
};

就讲到这里。

17-54 螺旋矩阵

题目链接：https://leetcode.cn/problems/spiral-matrix/description/?envType=study-plan-v2&envId=top-100-liked
难度：中等
解题日期：2026.1.26
标签：数组矩阵模拟
推荐题解：灵神的题解

这道题目也算是比较经典的模拟题目了。方法百花齐放，基本上都是找规律。

我找的规律是这样的：观察到螺旋矩阵输出时的行进方向为右->下->左->上的循环，于是就新建了两个分别负责x和y的方向数组，并且用一个指针来循环选择这四个方向。换方向的条件是这样的：如果按照当前方向行进，下标越界或者前方元素已经访问过，就说明我们需要转变方向了，就将这个指针循环+1，然后再判断一下+1后符不符合条件，如果按照新方向行进还是不符合条件，那就说明进入了死胡同，即全部元素都遍历完了。

上代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> dx = {0,1,0,-1};
        vector<int> dy = {1,0,-1,0};
        vector<int> ans;
        int p=0,x=0,y=0;
        int n = matrix.size(),m = matrix[0].size();
        vector<vector<bool>> visited(n,vector<bool>(m,false));
        while (true) {
            ans.emplace_back(matrix[x][y]);
            visited[x][y]=true;
            if (x+dx[p]<0 || x+dx[p]>=n || y+dy[p]<0 || y+dy[p]>=m || visited[x+dx[p]][y+dy[p]]) {
                p=(p+1)%4;
                if (x+dx[p]<0 || x+dx[p]>=n || y+dy[p]<0 || y+dy[p]>=m || visited[x+dx[p]][y+dy[p]]) break;
            }
            x+=dx[p];
            y+=dy[p];
        }
        return ans;
    }
};

当然，我的代码还是有优化空间的，可以将额外空间的这个visited矩阵改成边界的收缩，亦或是直接在原矩阵上标记，都可以将空间复杂度降低到O(1)。由于比较简单，就不再赘述。

18-48 旋转图像

题目链接：https://leetcode.cn/problems/rotate-image/description/?envType=study-plan-v2&envId=top-100-liked
难度：中等
解题日期：2026.1.27
标签：数组数学矩阵
推荐题解：灵神的题解

这道题就比较有意思了，同样也是找规律。

我们观察示例里面元素的位置变化，假设每个元素的坐标为(i,j)，很容易发现每个元素从(i,j)变到了(j,n-1-i)。

这里我是偷懒了，所以直接写了我发现的结论。如果难以发现规律，可以先看x轴坐标变化，再看y轴坐标变化，就和上方题解一样，慢慢来，会好一些。

知道了每个坐标的变化规律之后，就好办了...吗？我们需要原地变换数组，如果新开一个数组当然简单，无脑一直按照上面的规律取就行了。我们只能原地变换，注定我们只能交换两个元素(使用std::swap())，而直接交换是行不通的。

这时候就来到了这道题的核心：将上面的变化规律拆成两步边界分明的变化，变成(i,j)->(j,i)->(j,n-1-i)。

为啥要边界分明呢？我们需要保证我们的交换操作在每一对元素身上只会被进行一次，不会出现被换过去的元素被换回来的情况。

你看第一步，属于矩阵的斜对称，边界很明确，就是(i,i)这条斜线，这样我们在操作的时候，就能用循环很好的限定操作范围为矩阵的上三角。

第二步就更简单了，属于矩阵的左右对称(x轴不变，只变y轴)，边界也很分明，是矩阵的中线。不过找这根线还是有难度，我列了好几个式子才发现它是matrix.size()/2-1。

至此，思路毕。上代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        //(i,j)->(j,i)->(j,n-1-i)
        int m = matrix.size();
        //1. (i,j)->(j,i)
        for (int i=0;i<m;i++) {
            for (int j=i;j<m;j++) {
                swap(matrix[i][j],matrix[j][i]);
            }
        }
        //2.(j,i)->(j,n-1-i)
        for (int i=0;i<m;i++) {
            for (int j=0;j<=m/2-1;j++) {
                swap(matrix[i][j],matrix[i][m-1-j]);
            }
        }
    }
};

就讲到这里。

19-240 搜索二维矩阵 II

题目链接：https://leetcode.cn/problems/search-a-2d-matrix-ii/description/?envType=study-plan-v2&envId=top-100-liked
难度：中等
解题日期：2026.1.27
标签：数组二分查找分治矩阵
推荐题解：灵神的题解

这题就和前面的题目有些不一样了，单纯找规律可能很难找到解法。我甚至看了两遍题解才真正理解这题做法的关键所在。

看完第一遍题解，我领悟到了"收缩边界"和"分治"两个概念，在代码的开头定义了四个变量来圈定边界，甚至还在思考要不要用递归、边界条件怎么判断，如何退出...挺麻烦的。

于是我看了第二遍题解，才抓到这个做法的核心：只盯着右上角看，然后只收缩x轴的下界和y轴的上界。且听我娓娓道来。

首先，这个矩阵具有这样的特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

这就说明，如果某一列的第一个元素比我的目标元素大，那这一列一定没有我的目标元素，可以直接排除；同理，如果某一行的最后一个元素比我的目标元素小，那这一行也可以直接排除。

在这个做法里面，我们只盯着右上角的元素。按照上面的说法，如果这个元素比我的目标元素大，那就把右上角元素所在这一列排掉，y轴上界(数值高的那一边)减一，相当于往左边收缩一格；如果和目标相等，那就是找到了；如果比我的目标元素小，那就把右上角元素所在这一行排掉，x轴下界(数值低的那一边)加一，相当于往下面收缩一格。如此往复，直到右上角元素就是目标元素。如果边界收缩的越界了还没找到，那说明没找到，退出循环。

代码如下：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n=matrix.size(),m=matrix[0].size(),xl=0,xh=n-1,yl=0,yh=m-1;
        while (xh>=xl && yh>=yl) {
            int upRight = matrix[xl][yh];
            if (upRight>target) {
                yh--;
            }else if (upRight==target) {
                return true;
            }else {
                xl++;
            }
        }
        return false;
    }
};

顺带一提，为了方便寻找右上角的坐标，我的边界是设置为包含其本身的，也就是闭区间。

这个只盯着右上角的做法还是很巧妙的，把我看完题解第一遍的那些麻烦的边界判断想法全都免去了。

20-160 相交链表

题目链接：https://leetcode.cn/problems/search-a-2d-matrix-ii/description/?envType=study-plan-v2&envId=top-100-liked
难度：简单
解题日期：2026.1.28
标签：哈希表链表双指针
推荐题解：灵神的题解

既然这题是简单题，那我们长话短说。

题解都看完了吧？首先，我想到的是官方题解里面的第一种方法：哈希法，就是把链表A每个节点的指针都丢进无序集合里面，在遍历链表B的时候不断检查当前节点是否在这个集合里面(时间复杂度O(1))，第一个被检查出存在的节点就是两个链表相交的地方。

顺带一提，cpp的指针之间的比较比的是地址，和节点的值没有关系。这也是这个做法能不受题目中数字干扰的重要原因。

代码如下：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;


struct ListNode {
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(NULL) {
    }
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*> hash;
        ListNode* p = headA;
        while (p) {
            hash.emplace(p);
            p=p->next;
        }
        p=headB;
        while (p) {
            if (hash.count(p)) {
                return p;
            }
            p=p->next;
        }
        return nullptr;
    }
};

但是这个方法还是需要O(n)的额外空间，太吃内存了。那么我们该如何把它优化到O(1)的额外空间呢？答案就是双指针。也就是官方题解的方法2和灵神题解的方法。

这个方法其实挺浪漫的，就是：如果你走过我走过的路，我走过你走过的路，我们终会相遇。

不扯浪漫，数学原理其实也简单：

指针 pA 从 headA 开始走，指针 pB 从 headB 开始走。
当 pA 走到 headA 的末尾时，让它转场到 headB 的开头继续走。
当 pB 走到 headB 的末尾时，让它转场到 headA 的开头继续走。
奇迹时刻： 两个指针会在相交节点处相遇。

为什么？

假设 A 链表非相交部分长 a，B 链表非相交部分长 b，相交部分长 c。

指针 pA 走的距离：a + c (走完 A) + b (开始走 B 的非相交部分)
指针 pB 走的距离：b+c (走完 B) + a (开始走 A 的非相交部分)
结果： a + c + b = b + c + a。两者走的长度相等，刚好在相交点碰头！

当然，写的时候要注意，ab需要同时移动，就是你走一步我也走一步，即放在同个循环里面。

代码如下：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *pA,*pB;
        pA=headA;pB=headB;
        while (pA!=pB) {
            if (pA) pA=pA->next;
            else pA=headB;
            if (pB) pB=pB->next;
            else pB=headA;
        }
        return pA;
    }
};

就讲到这里。

21-206 反转链表

题目链接：https://leetcode.cn/problems/reverse-linked-list/description/?envType=study-plan-v2&envId=top-100-liked
难度：简单
解题日期：2026.1.28
标签：递归链表
推荐题解：灵神的题解

好一道数据结构题目。

长话短说吧，其实这道题就是链表的头插法。只不过并没有创建新链表，而是把这个节点本身给十分巧妙的原地使用了头插法，从而实现O(1)额外空间的链表反转。

直接上代码，上完代码之后再讲：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *cur = head,*pre=nullptr;
        while (cur) {
            auto nxt = cur->next; //是为了存储丢失的cur后继节点信息
            cur->next = pre;
            pre=cur;
            cur=nxt;
        }
        return pre;
    }
};

头插法，顾名思义，我们需要把新元素给插在头节点的前面，并且新元素本身成为头节点。因此，如果将一个序列按照从左到右的顺序，使用头插法插入链表当中，自然而然就实现了反转的效果。

在这道题的题解代码中，我们使用了pre作为前驱节点(也算是反转后链表的后继节点)，cur作为当前节点，我们的目标就是，既保证cur能够沿着当前链表的方向往后走，又能让它的前驱节点成为它的后继。这时候我们就需要一个中间变量来暂时存储cur的后继，以确保cur在指向pre之后，还能继续往后走。

在往后走之前，由于当前节点到了下一个节点就变成了前驱节点，因此需要用pre存储一下当前节点，然后cur再往后走。

大体思路就是这样，虽说是头插法，但是原地头插反转链表的算法我还是第一次见，挺新奇的。这题还有个做法是递归法，是灵神题解里面的第一种方法，我这边就不讲了，感兴趣的同学自己去探索吧。

22-234 回文链表

题目链接：https://leetcode.cn/problems/palindrome-linked-list/description/?envType=study-plan-v2&envId=top-100-liked
难度：简单
解题日期：2026.1.29
标签：栈递归链表双指针
推荐题解：灵神的题解

这道题还是比较有意思的，从灵神的题解看来，我们需要做两道前置题目：反转链表和链表的中点。前者就是上一道题，后者我还确确实实没做过。

当然，按照我一贯欧美的作风，我肯定是不会去做那道题的。于是我直接看了一眼代码，好像也不是很难。那就直接讲吧。

首先讲讲前置知识：如何找到链表的中点？总体思路很简单：使用快慢指针。快指针一次往后两格，慢指针一次往后一格，当块指针无法继续往后两格时(要么指向最后一个节点，要么指向null)，慢指针指向的位置就是链表的中点(如果是奇数长度，那就是正中央；如果是偶数长度，那就是中线偏右的那个节点)。

这道题为啥需要用到上面两道前置题目呢？因为我们需要先找到链表的中点，然后再将链表的后半段原地反转，反转完之后，就相当于一个链表先被劈成两半，然后被反转之后，后一半的尾巴和前一半的尾巴可能重叠(链表长度为奇数)，也可能各自分离(链表长度为偶数)。

然后呢，我们就可以从这两个新链表的头部开始，一步一步往后同时遍历，一边遍历一边比较，若有不相等就直接返回false，两条链表都遍历完了就返回true。

思路讲完了，上代码：

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        //1.先找链表中点
        ListNode *slow=head,*fast=head;
        while (fast && fast->next) {
            slow=slow->next;
            fast=fast->next->next;
        }
        //2.反转后半段
        ListNode *pre=nullptr,*cur=slow;
        while (cur) {
            ListNode *nxt = cur->next;
            cur->next = pre;
            pre=cur;
            cur=nxt;
        }
        //3.开始比较
        ListNode *p1=head,*p2=pre; //这里需要注意，后半部分反转后的链表的头结点是pre，不是cur，cur已经指向null了
        while (p1 && p2) {
            if (p1->val!=p2->val) return false;
            p1=p1->next;
            p2=p2->next;
        }
        return true;
    }
};

其实完全可以像灵神题解里面一样，把上面两道前置知识的题目封装在函数里面，然后直接调用获取后半反转后链表的头结点即可。

23-141 环形链表

题目链接：https://leetcode.cn/problems/linked-list-cycle/description/?envType=study-plan-v2&envId=top-100-liked
难度：简单
解题日期：2026.1.29
标签：哈希表链表双指针
推荐题解：灵神的题解

这道题的做法也是挺妙的：利用了操场上跑的慢的人一定会被跑的快的人"套圈"的原理。

那么我们就能很自然的联想到快慢指针用快慢指针来做这道题。

当然，看到题目第一眼，我是没想出来要这样做的。瞟了一眼题解才突然恍然大悟。

"套圈"的概念，具象化到这道题，其实也简单：如果快指针到终点了也没和慢指针相等过，说明无环；由于只要不到终点，就会一直走，所以如果快指针和慢指针在某一时刻相等了，就说明是环，直接返回true。

上代码：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow=head,*fast=head;
        while (fast && fast->next) {
            slow=slow->next;
            fast=fast->next->next;
            if (fast==slow) return true;
        }
        return false;
    }
};

就讲到这里。

24-142 环形链表 II

题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/?envType=study-plan-v2&envId=top-100-liked
难度：中等
解题日期：2026.1.30
标签：哈希表链表双指针
推荐题解：灵神的题解

从题号也可以看出来，上面这道题就是这道题的前置题目。也是，毕竟我们得先判断题目给的链表是不是环，才能进行下一步。

那么在套用上面这道题的方法，判断完这个链表是不是环之后，我们下面该怎么找链表入口呢？并且只用O(1)的额外空间。

一开始我也想不出来，看了题解还是理解了大半天，也终于是理解了。其实还是快慢指针。

从灵神的题解偷一张图过来。

题解文字描述的上半段没啥问题，很好理解，我相信大多数同学(包括我自己)的理解问题都主要出现在下半段文字吧？那我换个方式讲一下。

首先，由于快指针的速度是慢指针的2倍，当他们相遇时，快指针走过的总距离一定是慢指针的2倍，因此前者2b后者b，这很好理解。

然后，由于是套圈，于是快指针比慢指针多走的那部分距离(即2b-b=b)一定一定一定是这个环长度的整数倍。

因此，这里我们可以获得一个很重要的结论：因为b是环长度的整数倍，所以，从这个环上某一点开始，往后走b步，一定会回到原地。

再回到上面这张图，是不是回想起来了？b同时也是链表起点到相遇点的距离！

然后呢，由于我们要求的环的入口距离起点的距离是a，并且我们还得直接返回这个节点，于是我们就要想办法让这两个指针一起指向这个节点。

这如何做到呢？我们可以把快慢指针其一(这里我选择慢指针)丢回起点，然后把快指针留在相遇点，然后让它们继续往后以相同的速度走。这时候会发生什么呢？先看慢指针这边，相较于起点走了a步，会到入环的节点；再看快指针这边，它站在相遇点，如果它也再走a步，再加上它之前走了b步，那么它相较于起点走过的总路程就是b+a步。还记得b是环长度的整数倍吗？这就说明，相较于起点走了b+a步就和走了a步的效果是一模一样的。换句话说，走a步之后，快指针也会到达入环节点！

这时候，我们直接挑选快慢指针其一返回即可。这道题的逻辑确实挺绕的。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        //1.先判是否为环
        ListNode *slow=head,*fast=head;
        bool flag=false;
        while (fast && fast->next) {
            slow=slow->next;
            fast=fast->next->next;
            if (slow==fast) {
                flag=true;
                break;
            }
        }
        if (!flag) return nullptr;
        //2.把slow放回起点，各自一步一步走，再次汇聚即为入环点
        slow=head;
        while (slow!=fast) {
            slow=slow->next;
            fast=fast->next;
        }
        return slow;
    }
};

就讲到这里。

25-21 合并两个有序链表

题目链接：https://leetcode.cn/problems/merge-two-sorted-lists/description/?envType=study-plan-v2&envId=top-100-liked
难度：简单
解题日期：2026.1.30
标签：哈希表链表双指针
推荐题解：无

这道题也是一道经典的数据结构题目，总体思路很简单，和合并两个升序数组一样：维护两个指针，都指向两条链表的头部，每次都选小的那个插在新链表的头部。

对，基本思路就这么多，然后我去实现了，欧美打法，自信满满的写了一坨史山代码：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *p1=list1,*p2=list2,*list3 = nullptr;
        //1.选择头结点
        if (p1 && p2) {
            if (p1->val<p2->val) {
                list3=p1;
                p1=p1->next;
            }else {
                list3=p2;
                p2=p2->next;
            }
        }else {
            if (p1) {
                list3=p1;
                p1=p1->next;
            }else if (p2){
                list3=p2;
                p2=p2->next;
            }else {
                return nullptr;
            }
        }
        ListNode *p3=list3;
        //2.开始两头工作
        while (p1 || p2) {
            if (p1 && p2) {
                if (p1->val<p2->val) {
                    p3->next=p1;
                    p1=p1->next;
                }else {
                    p3->next=p2;
                    p2=p2->next;
                }
            }else if (p1) {
                p3->next=p1;
                p1=p1->next;
            }else if (p2) {
                p3->next=p2;
                p2=p2->next;
            }
            p3=p3->next;
        }
        //3.收尾与返回
        p3->next=nullptr;
        return list3;
    }
};

基本思路就是写了一堆复杂逻辑，先确定头结点，然后再用差不多的逻辑把小的优先接在链表头，最后再收尾返回头结点。

但是其实根本不需要这么麻烦。

我们引入哨兵的概念：新定义一个空白节点作为头结点，它的next指向null，这样就可以跳过开头的选头结点的过程了，直接进循环开插。

循环里面的逻辑也可以大大简化：我们只处理两个链表都没遍历完的情况，正常比较取小插入即可。

当其中一个链表跑完之后，再把剩下没跑完的链表直接接在新链表的尾部，不需要再重新遍历了，要学会利用链表的特性。

基本思路就是这样，上代码：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(0);
        ListNode *tail = &dummy;
        while (list1 && list2) {
            if (list1->val<list2->val) {
                tail->next=list1;
                list1=list1->next;
            }else {
                tail->next=list2;
                list2=list2->next;
            }
            tail=tail->next;
        }
        if (list1) {
            tail->next=list1;
        }else {
            tail->next=list2;
        }
        return dummy.next;
    }
};

就讲到这里。

最后修改：2026 年 01 月 30 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

名称 *

🎲

邮箱 *

地址

LeetCode Hot100解题笔记 260130更新

2810873701@qq.com • 2025 年 12 月 15 日

<h1>前言</h1>有点惊讶吧？这个Hot100解题笔记还是提前到来了。因为呢，dp题单实在是太多了，然后面试题又有大部分都出现在Hot100里面。我的目标是把hot100刷个2遍左右，所以我准备现在抢跑：将dp题单和hot100同时往前推(在文章创建的时候是这样的，后面我猜可能dp会先停下来，然后继续推hot100)。话不多说，下面直接开始解题！PS：下面的数字格式是序号-力扣的题目编号，解题语言默认cpp。<h1>1-1 两数之和</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/two-sum/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/two-sum/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：简单解题日期：2025.12.15标签：数组 哈希表</blockquote>虽说这是一道简单题，直接套双重循环也能过，但是这样总是差点意思。我是看了一眼题目的提示才知道要用哈希表(注意！<code>unordered_map</code>才是哈希表，<code>map</code>不是！)。基本逻辑就是，利用哈希表查找速度O(1)的特性，把数组和下标对应丢进映射，然后遍历数组，将target与当前元素作差，然后在映射里面查找这个：如果找得到，就取出两个下标返回；如果找不到，就接着往下找，总能找到的。然后呢，题目不允许取同一个下标两次，所以还得在取出下标的时候判断一下是否和当前下标相等，不然不能取。至于你们可能担心的数组有重复数字的问题，不用担心，下面的代码在写映射的时候默认保留的是那个数字最大的下标，而我们遍历是从前往后遍历的，就算这是唯一解也凑得出。是不是有点bug+bug=没有bug的感觉了哈哈哈上代码：<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
 vector&lt;int&gt; twoSum(vector&lt;int&gt;&amp; nums, int target) {
 unordered_map&lt;int,int&gt; dict;
 //1.给数字-下标对放进哈希映射
 for (int i=0;i&lt;nums.size();i++) {
 dict[nums[i]] = i;
 }
 //2.遍历找搭配
 for (int i=0;i&lt;nums.size();i++) {
 int x = target-nums[i];
 if (dict.count(x)&gt;0 &amp;&amp; dict[x]!=i) {
 return vector&lt;int&gt;{i,dict[x]}; //题目说返回顺序随意，所以我就懒得排序了
 }
 }
 return vector&lt;int&gt;{0,0}; //这一行是为了防止报错，题目用例保证有且只有一个答案，所以不会走到这里的
 }
};</code></pre><h1>2-49 字母异位词分组</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：中等解题日期：2025.12.15标签：数组 哈希表 字符串 排序</blockquote>这题还是挺有意思的，你看标签就知道了，需要先把每个字符串排序，这样才能知道它们互相之间是不是字母异位词。那么怎么排序呢？我目前学过的语言有Python，Go，Cpp这三个，其中前两者的字符串(string)类型都是不可变的，但是cpp的string属实是让我大开眼界了：不但可变(支持用sort排序)，而且还能拿来作为哈希表映射的键(可哈希)，这写起来不要太舒适。所以，用cpp做这道题，直接遍历一遍字符串数组，然后对每个字符串直接使用sort就行了，非常方便。然后下面的逻辑可能稍微有点绕，我干讲也不太好讲，直接在注释里面和代码一起讲好了。<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
 vector&lt;vector&lt;string&gt;&gt; groupAnagrams(vector&lt;string&gt;&amp; strs) {
 //1.拷贝一份字符串数组，并给每个字符串排序
 auto strs2 = strs; //这里用于存放唯一的字母异位词，大概率会出现一堆重复的字符串(从题目的用例来看)
 for (auto &amp; s : strs2) {
 sort(s.begin(),s.end());
 }
 //2.使用哈希表管理二维数组的插入和下标管理
 unordered_map&lt;string,int&gt; dict; //这个映射存放已经插入的字符串在ans数组中的位置
 vector&lt;vector&lt;string&gt;&gt; ans; //存放答案的二维数组
 //这里用位置遍历是利用了strs和strs2的唯一字母异位词与原字符串的对齐，方便取出原字符串
 for (int i=0;i&lt;strs.size();i++) {
 if (dict.count(strs2[i])==0) { //如果在dict里面没找到这个唯一的字母异位词，说明是新创建
 dict[strs2[i]]=ans.size(); //将这一系列字母异位词在ans数组中的位置存进dict
 ans.emplace_back(vector&lt;string&gt;{strs[i]}); //然后插入新的一行字符串数组
 } else { //如果有，只需找到对应的下标然后插入即可
 ans[dict[strs2[i]]].emplace_back(strs[i]); 
 //从dict中取出这一系列的字母异位词所在的ans数组的下标，然后插入最新的字母异位词
 }
 }
 return ans;
 }
};
</code></pre>看懂了吧？总结一下，就是利用排序后strs2数组中的字母异位词的唯一性，将其与strs中的原字符串相匹配，再配合映射进行它在ans二维数组中插入位置的管理，从而形成了有点小绕的逻辑闭环。<h1>3-283 移动零</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：简单解题日期：2025.12.16标签：数组 双指针</blockquote>好久没做双指针的题目了，虽说这道题的难度是简单，并且我看到题目没几秒钟就想到了用额外空间该怎么做。但是题目要求原地修改数组。我真求你了。然后我又想了一会，想出了用一个指针找0，另一个指针负责把后面的元素一个个往前挪到前面的指针指向的位置把0盖掉，纯纯的用时间复杂度换空间复杂度，我真没招了。然后咨询了一下ai，也算是回到了正轨：使用快慢指针模型来解决这道题目。啥是快慢指针模型？<blockquote>“快慢指针 - 读写模型”（或者叫“填充/覆盖模型”）：<ul><li>快指针 (Reader)：负责读数据，判断这个数据要不要保留。</li><li>慢指针 (Writer)：负责写数据，始终指向“下一个有效数据的存放位置”。</li></ul></blockquote>在这道题目里面，快指针(下面统称为fast)负责寻找非0元素，而慢指针(下面统称为slow)负责寻找fast指针找到的非0元素的存放位置。基本逻辑是这样的：fast一直往后挪，不停，所以直接用for循环就行；slow只有在fast找到非0元素时，才会将fast和slow所指元素交换，然后往后挪一位。并且，这个设计非常精妙，保证了当发生交换时只有以下两种情况：要么是slow指向0，fast指向非0，要么是fast和slow一起指向同一个非0元素，也就是进行了"原地交换"，无事发生。这是如何保证的呢？因为在上面的逻辑里面，假设当前fast和slow都指向一个非0元素，而下一个元素就是0，然后按照逻辑，fast和slow都往后挪一位，此时slow就自然指向了0。然后呢，由于fast是一直往后的，所以下一轮循环，由于fast指向了0，所以，slow不会往后。这样自然而然，就使得fast指向非0而slow指向了0。也可以这么理解：slow只是正在维护非0元素的边界(有点像插入排序，都是维护已处理-未处理的边界)。当 fast 和 slow 错开时，slow 和 fast 中间夹着的那个区域（即 <code>nums[slow...fast-1]</code>），全都是 0。这就解释了为什么要把 <code>nums[fast]</code> 换过来——因为要把中间的这堆 0 往后挤！这样逻辑就很清楚了吧？看代码：<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
 void moveZeroes(vector&lt;int&gt;&amp; nums) {
 int slow=0;
 for (int fast=0;fast&lt;nums.size();fast++) {
 if (nums[fast]!=0) { //只有遇到非0才会往后挪slow
 swap(nums[fast],nums[slow]);
 slow++;
 }
 }
 }
};</code></pre>总结：一旦遇到数组原地筛选/移除/移动类题目，直接套用：Fast 找目标，Slow 守坑位。<h1>4-128 最长连续序列</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：中等解题日期：2025.12.17标签：并查集 数组 哈希表</blockquote>这是STL库被资本(LeetCode)做局的一题。这道题的思路是很简单的：利用哈希表查询速度O(1)的特性，将本来O(n^2)的双指针暴力查询降级到O(n)的时间复杂度。首先给所有元素都丢进<code>unordered_set</code>里面，顺带着还自动去重；然后呢，遍历<code>nums</code>数组，利用集合的count方法，另外开一个循环查询集合里面是否有当前元素x+1,x+2...x+n，由此得出长度就是n。但是呢，这样会产生大量无用的查询：我后面遍历到x+1，亦或是x+2，甚至到x+n，都会重新执行一遍这个逻辑，给时间复杂度又退化成O(n^2)了，这可不行。解决方法也很简单：在进入这个循环之前，检查集合里面是否有当前元素x-1。如果有，说明这绝对不是某个序列的开头，就自然不会重复进入了。你是不是以为这样就完事了？我也是这么想的，我的第一版代码就是这样的：<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
 int longestConsecutive(vector&lt;int&gt;&amp; nums) {
 unordered_set&lt;int&gt; uSet;
 //1.给数字丢进去
 for (auto &amp;x:nums) {
 uSet.emplace(x);
 }
 //2.开始遍历
 int maxLength = 0;
 for (auto &amp;x:nums) {
 if (uSet.count(x-1)==0) { //防止重复操作，保证这个数就一定是开头
 int cnt=0;
 while (uSet.count(x+cnt)) {
 cnt++;
 }
 maxLength = max(maxLength,cnt);
 }
 }
 return maxLength;
 }
};</code></pre>然后粘贴到力扣，先测用例，完美，全票通过，然后提交——超时。我就疑惑了，为啥呢？一问ai，我自己也没绷住：<blockquote>你的算法逻辑其实是非常优秀的，思路完全符合 O(n) 的要求。你的代码会超时（TLE），主要原因是 C++ 标准库中 <code>unordered_set</code> 的底层实现问题，导致遭到针对性数据的“哈希碰撞攻击”。这里有两个主要原因，按影响大小排序：<h3>1. 哈希碰撞（主要原因）</h3>LeetCode 的测试用例中包含针对 C++ <code>std::unordered_set</code> 默认哈希函数的“恶意数据”（例如大量的哈希冲突数据）。<ul><li>正常情况： 哈希表的增删查改是 O(1)的。</li><li>最坏情况： 当大量数字映射到哈希表的同一个“桶”时，哈希表会退化成链表，操作复杂度变成 O(n)。</li><li>结果： 你的整体复杂度从 O(n) 退化到了 O(n^2)。</li></ul><h3>2. 重复元素遍历（次要原因）</h3>你现在的代码是遍历原始数组 nums：for (auto &x:nums)。如果输入数组是 [1, 1, 1, ..., 1]（比如 10万个 1），虽然你有 if (uSet.count(x-1)==0) 的判断，但你仍然对这 10万个重复的数字都执行了一次哈希查询 count(x-1)。</blockquote>一看把我卡住的用例，还真是：<pre><code>[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,(此处省略),24933,24934,24935,24936,24937,24938,24939,24940,24941,24942,24943,24944,24945,24946,24947,24948,24949,24950,24951,24952,24953,24954,24955,24956,24957,24958,24959,24960,24961,24962,24963,24964,24965,24966,24967,24968,24969,24970,24971,24972,24973,24974,24975,24976,24977,24978,24979,24980,24981,24982,24983,24984,24985,24986,24987,24988,24989,24990,24991,24992,24993,24994,24995,24996,24997,24998,24999,25000,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,00,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,(此处省略),0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]</code></pre>如果按照原来的方法遍历数组，会发生上面所提到的"对这 10万个重复的数字都执行了一次哈希查询 count(x-1)"的情况。所以，更改也很简单：把下面遍历的主题从<code>nums</code>改成<code>uSet</code>就行：<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
 int longestConsecutive(vector&lt;int&gt;&amp; nums) {
 unordered_set&lt;int&gt; uSet;
 //1.给数字丢进去
 for (auto &amp;x:nums) {
 uSet.emplace(x);
 }
 //2.开始遍历
 int maxLength = 0;
 for (auto &amp;x:uSet) { //避免重复遍历过量元素，改为遍历保证无重复的集合
 if (uSet.count(x-1)==0) { //防止重复操作，保证这个数就一定是开头
 int cnt=0;
 while (uSet.count(x+cnt)) {
 cnt++;
 }
 maxLength = max(maxLength,cnt);
 }
 }
 return maxLength;
 }
};</code></pre>挺有意思，之前还没遇到过因为这种原因超时的情况。<h1>5-11 盛最多水的容器</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/container-with-most-water/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/container-with-most-water/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：中等解题日期：2025.12.18标签：贪心 数组 双指针推荐题解：<a class="no-external-link" href="https://leetcode.cn/problems/container-with-most-water/solutions/94102/on-shuang-zhi-zhen-jie-fa-li-jie-zheng-que-xing-tu" target="_blank">https://leetcode.cn/problems/container-with-most-water/solutions/94102/on-shuang-zhi-zhen-jie-fa-li-jie-zheng-que-xing-tu</a></blockquote>上面的题解可以看一下，正确性证明讲的非常好，简直是神级题解。所以下面我就不再赘述这个题目做法的正确性了，讲讲我自己的看法。首先，为啥初始化选择左右指针分布在数组的两端？答案显而易见，就是初始保证它的长度(d)是最长的。然后，如何移动左右指针呢？假设左边的木板的高度(<code>h[l]</code>)比右边的高度(<code>h[r]</code>)低。此时，我们有两种选择：<ol><li>移动左边的指针：<code>l++</code>。由于不管移动左边还是右边，长度都是d-1，所以面积的大小就由两边最短的木板决定了。并且呢，无论左边的指针怎么动，左边的木板高度变成咋样，根据木桶效应，决定面积的那个木板的高度绝对不会超过右边的木板。已知左边的高度就是比右边低，所以挪动l，木板的高度(<code>h[l]</code>)可能会变大，也可能会变小。如果<code>h[l]</code>变小，已知<code>d-&gt;d-1</code>，所以面积一定会变小；如果<code>h[l]</code>变大，虽然<code>d</code>变小了，但是只要<code>h[l]</code>变的足够大，大到抵消<code>d</code>的损失，面积还是有可能反而变大的。总结：移动左边的指针，面积可能变大也可能变小，相当于搏一搏，找个机会。</li><li>移动右边的指针：<code>r--</code>。这就非常不一样了。已知<code>h[l]&lt;h[r]</code>，如果把这个高的木板淘汰了，根据木桶效应，决定面积的那个木板的高度绝对不会超过左边的木板。是不是有点感觉了：这相当于强行把面积的上限压低了！咱们讨论一下：如果<code>h[r-1]&gt;h[r]</code>，那么面积变小，因为<code>h[l]&lt;h[r]</code>，所以决定高度的是<code>h[l]</code>，并且d变小了；如果<code>h[r-1]&lt;h[r]</code>，那么面积还是变小，原因显而易见了吧。总结：移动右边的指针，面积只会变小或者不变，没有赢面。</li></ol>总结：移动短板，是为了寻找面积变大的唯一可能性；放弃短板，是因为以它为边界的所有其他可能方案都已被证明更差。上代码：<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
 int maxArea(vector&lt;int&gt;&amp; height) {
 int maxArea = 0,l = 0,r = height.size()-1;
 while (l&lt;r) {
 maxArea = max(min(height[l],height[r])*(r-l),maxArea);
 if (height[l]&lt;height[r]) l++;
 else r--;
 }
 return maxArea;
 }
};</code></pre><h1>6-15 三数之和</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：中等解题日期：2025.12.21标签：数组 双指针 排序推荐题解：官方题解不太行，还是Gemini的做法更加简单明了</blockquote>这题，我的第一个思路并不是我现在的做法：由于Hot100刚刚做完哈希表的题目(见<a class="no-external-link" href="https://leetcode.cn/problems/two-sum/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">1.两数之和</a>)，然后又看到这道题的提示：把三指针转化成双指针的问题。那不是把三数之和的问题转化成两数之和的问题，然后再用上面这道题目的哈希表做法来做两数之和的问题，把时间复杂度压到O(n^2)。想法很美好，我代码也写出来了，如下：<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
 vector&lt;vector&lt;int&gt;&gt; threeSum(vector&lt;int&gt;&amp; nums) {
 int n = nums.size();
 //1.将全部数丢进哈希
 unordered_map&lt;int,int&gt; dict;
 unordered_set&lt;string&gt; filter;
 for (int i=0;i&lt;n;i++) {
 dict[nums[i]]=i;
 }
 //2.开始遍历
 vector&lt;vector&lt;int&gt;&gt; ans;
 for (int x=0;x&lt;n;x++) {
 int v1 = -nums[x]; //y+z的期望值
 for (int y=0;y&lt;n;y++) {
 int v2 = v1-nums[y]; //z的期望值
 if (dict.count(v2)) {
 int z = dict[v2];
 if (z!=y &amp;&amp; y!=x &amp;&amp; z!=x) {
 vector&lt;int&gt; temp = {nums[x],nums[y],nums[z]};
 sort(temp.begin(), temp.end());
 int nx = temp[0],ny = temp[1],nz = temp[2];
 string str = to_string(nx)+&quot;-&quot;+to_string(ny)+&quot;-&quot;+to_string(nz); //用字符串拼接来去重
 if (!filter.count(str)) {
 ans.emplace_back(vector&lt;int&gt;{nx,ny,nz});
 filter.emplace(str);
 }
 }
 }
 }
 }
 return ans;
 }
};</code></pre>时间复杂度妥妥的O(n^2)啊！但是还是超时了：311 / 315，因为字符串拼接既费时间又费空间。Confused，那我就去问了Gemini，它给的做法非常好理解，我来讲讲。首先呢，做法有点类似于上一道题<a class="no-external-link" href="https://leetcode.cn/problems/container-with-most-water/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">11.盛最多水的容器</a>。我们先把这个数组升序排序。这是为了：<ol><li>方便去重。在排序之后，相同的元素会排在一起，可以很方便的避免开头重复的情况。</li><li>利用单调性。排序是我下面即将讲的操作的前提。</li></ol>首先，提示没说错，我们确实需要将三数之和转换成两数之和。所以，最外层的循环，我们维护一个i，指向三个数的第一个数。然后呢，后面两个数，我们采用类似于11题(上方有链接)的"收缩法"来完成：维护两个指针，<code>l=i+1</code>和<code>r=n-1</code>，指向i指向的这个数的后面区域的数的头和尾，相当于最小和最大的数。然后我们计算<code>sum=nums[i]+nums[l]+nums[r]</code>。分类讨论：<ol><li>如果<code>sum&gt;0</code>，那说明选的数大了，我们需要选更小的。将大的数换掉，<code>r--</code>。</li><li>如果<code>sum&lt;0</code>，那说明选的数小了，我们需要选更大的。将小的数换掉，<code>l++</code>。</li><li>如果<code>sum=0</code>，说明这三个数是正确答案，那就将它们丢进答案数组<code>ans</code>。</li></ol>然后还有一个很重要的剪枝优化，也是利用了排序之后数组的单调性：如果<code>nums[i]&gt;0</code>，直接<code>break</code>。因为如果这个数都大于0了，后面的待选择区域的数肯定全部都大于0，是绝对没有正确答案的，后面就没有继续下去的必要了。到这里，题目的基本思路就差不多讲完了，但是程序现在还是不能跑出正确答案。那么现在肯定有同学要问了：去重的部分在哪里？答：在主指针i，左右指针收缩的过程中，我们都可以很方便的利用"重复的数都挤在一起"这个特性来去重。当主指针i刚刚往后挪了一位，进入下一个循环时：如果<code>i&gt;0 &amp;&amp; nums[i]==nums[i-1]</code>，那么说明一模一样的逻辑在前一个数已经进行过了，我们就得跳过这一次循环，防止重复。那么为啥不是和后面的数比呢？因为如果跟后面比（<code>nums[i] == nums[i+1]</code>），会把 <code>[-1, -1, 2]</code> 这种三元组内部允许重复元素的情况给错杀掉。在左右指针收缩的过程中，如果我们找到了正确答案，在将答案丢进数组后，我们继续利用这个特性，开个条件为<code>l&lt;r &amp;&amp; nums[l]==nums[l+1]</code>的循环(右指针同理)，保证左右指针都不是已经处理过的数。到这里，这道题目才算完整。我们可以发现，找三个加起来为0的数本身不难，难在如何优雅的去重。这个做法用简单的"收缩"和"位移"，在解题目的同时还顺便把重给去了，十分优雅。下面看代码：<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
 vector&lt;vector&lt;int&gt;&gt; threeSum(vector&lt;int&gt;&amp; nums) {
 int n = nums.size();
 //1.给数组排序
 sort(nums.begin(), nums.end());
 //2.开始寻找三个数
 int l=0,r=0;
 vector&lt;vector&lt;int&gt;&gt; ans;
 for (int i=0;i&lt;n;i++) {
 if (nums[i]&gt;0) break;
 if (i&gt;0 &amp;&amp; nums[i]==nums[i-1]) continue;
 l = i+1;
 r = n-1;
 while (l&lt;r) {
 int sum = nums[i]+nums[l]+nums[r];
 if (sum==0) {
 ans.emplace_back(vector&lt;int&gt;{nums[i],nums[l],nums[r]});
 while (l&lt;r &amp;&amp; nums[l]==nums[l+1]) l++;
 while (l&lt;r &amp;&amp; nums[r]==nums[r-1]) r--;
 l++;
 r--;
 }
 if (sum&gt;0) r--;
 if (sum&lt;0) l++;
 }
 }
 return ans;
 }
};</code></pre>那这道题到这里就讲完了。<h1>7-3 无重复字符的最长子串</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：中等解题日期：2025.12.23标签：哈希表 字符串 滑动窗口推荐题解：无</blockquote>惊不惊喜？意不意外？时隔4个月，滑动窗口限时返厂！PS：如果你对滑动窗口感兴趣，你可以去看我25年8月暑假写的<a href="https://blog.lecspace.com/index.php/archives/76/">滑动窗口算法笔记</a>，那时候我还在用Go刷题，现在感觉是真不如C++一根。由于时隔的时间太长，我已经忘记了这种题型的滑窗的大多数细节，并且一翻我的笔记，我发现我做过这道题，并且是用暴力枚举双指针的方式做的，时间复杂度O(n^2)。但是我的潜意识又告诉我，这道题可以用O(n)的方法解决，一翻我自己的笔记，还真让我翻到了：<blockquote>第二种 条件移动左边界型 时间复杂度O(n)基本原理是这样的：<blockquote>只遍历滑窗的右边界。向右扩大滑窗，左边界一直不动，同时一直做符合题目要求的某种统计（计数等）。如果这个滑窗满足条件，就一直更新它的最大长度；如果不满足条件了，那就把左边界一直往右推，缩小滑窗，直到满足条件，如此往复。</blockquote>看代码：<pre><code class="lang-go">maxLength := 0
l := 0 //左边界
for r := 0; r &lt; len(nums); r++ { //遍历右边界
 //在这里处理逻辑
 for hash[nums[r]] &gt; k { //一直移动左边界，直到符合条件为止
 //处理逻辑
 l++
 }
}</code></pre>这种方法的好处就是很快，时间复杂度O(n)，坏处就是不一定所有题目都能用。</blockquote>代码框架大致没啥问题，但是在这道题我们不能直接照搬：因为我初步打算使用<code>unordered_set</code>的自动去重功能来判断我后入窗的元素是否为重复元素，如果还是先处理加加减减的逻辑再移动左指针，会有问题——那么这个已经存在在集合中的元素，如果还要强行emplace，啥也不会发生，相当于这个元素被吞掉了。为了防止元素被吞，我们需要调换一下上述框架循环和处理右指针加加的逻辑的位置。直接上代码，有详细注释：<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
 int lengthOfLongestSubstring(string s) {
 unordered_set&lt;char&gt; hash; //初始化集合
 int l=0,maxAns=0; //初始化左指针、最大答案
 for (int r=0;r&lt;s.size();r++) { //右移右指针
 while (hash.count(s[r])) { //如果右指针指向的当前元素在集合里面，说明再加就不是无重复字符的子串了
 hash.erase(s[l]); //删掉左指针当前指向的元素
 l++; //右移左指针
 }
 hash.emplace(s[r]); //将右指针指向的当前元素加入集合中
 maxAns = max(maxAns,r-l+1); //维护最大答案
 }
 return maxAns;
 }
};</code></pre>到这里，这题就讲解完毕了(顺带吐槽一下Typecho的编辑器，只要代码块下面没别的东西，我就没法在下面插入新内容。这也是我另外打这行字的主要原因)。<h1>8-438 找到字符串中所有字母异位词</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：中等解题日期：2025.12.25标签：哈希表 字符串 滑动窗口推荐题解：<a class="no-external-link" href="https://leetcode.cn/problems/find-all-anagrams-in-a-string/solutions/2969498/liang-chong-fang-fa-ding-chang-hua-chuan-14pd/?envType=study-plan-v2&envId=top-100-liked" target="_blank">灵神对这道题的题解</a></blockquote>我们继续滑动窗口。这道题也算是打破了我灵神滑动窗口题单的一个窟窿了，我在题单里面没遇到过这种类型的题目。不过呢，"异位词"这个概念，我们在上面的<a class="no-external-link" href="https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">第2题</a>已经遇到过了，当时用的是排序的思维，于是在初做这道题时，我的第一反应就是去排序：维护一个定长滑窗，再<code>substr()</code>截取子串，最后直接使用<code>sort()</code>进行排序。但是一看题目的数据范围：<code>1 &lt;= s.length, p.length &lt;= 3 * 10^4</code>。我真求你了，排序的时间复杂度是O(nlogn)，再叠加滑窗的O(n)复杂度，总体时间复杂度来到了O(n^2logn)，面对这样的数据规模还是太慢了。所以，这题我们得放弃排序了。那么题目没说字母不重复，也就是说这个字符串中的字母是有可能重复的，我们该如何快捷方便的确认两个字符串是否是"字母异位词"呢？我一开始是没想到的，看了一眼题解豁然开朗：统计每个字母出现的次数，如果每个字母出现的次数一模一样，说明就是异位词！既然是计数，就有了两种选择：要么选<code>unordered_map</code>，要么选<code>vector</code>，要么退而求其次用原生数组(需要自己写比较的逻辑)。我的代码选的是<code>vector</code>，套用经典滑窗模板(左出右进，<del>不会的去看我博客的滑窗算法笔记</del>)即可：<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
 vector&lt;int&gt; findAnagrams(string s, string p) {
 vector&lt;int&gt; ans;
 vector&lt;int&gt; cnt(26,0),key(26,0);
 for (auto&amp; x:p) key[x-'a']++;
 //这里有个小坑点：如果不加int的强转，由于size()方法返回的是无符号整数，它不存在负数，假设2-3，结果不是-1而是1
 //所以在p比s长的时候，要么直接开头特判返回空数组，要么就在这里强转，让循环不进入，更推荐我现在的做法吧
 for (int l=0;l&lt;=(int)s.size()-(int)p.size();l++) {
 if (l==0) {
 for (int i=0;i&lt;p.size();i++) {
 cnt[s[i]-'a']++;
 }
 }else {
 cnt[s[l-1]-'a']--;
 cnt[s[l+p.size()-1]-'a']++;
 }
 if (cnt==key) { //利用vector的比较操作符
 ans.emplace_back(l);
 }
 }
 return ans;
 }
};</code></pre>当然，我也请教了gemini：如果把<code>vector</code>换成其他数据结构会发生啥？<blockquote><ol><li>换成 <code>std::unordered_map&lt;char, int&gt;</code></li></ol>结论：性能会显著下降。<ul><li>原因 1：哈希开销。 <code>unordered_map</code> 每次存取都需要计算 <code>hash(key)</code>。对于只有 26 个连续字符的情况，直接通过 <code>x - 'a'</code> 索引数组是 $O(1)$ 且常数极小的，而哈希表常数项很大。</li><li>原因 2：内存分布。 <code>unordered_map</code> 的桶（buckets）通常分散在堆内存中，对 CPU 缓存（L1/L2 Cache）不友好；而数组在内存中是连续的。</li><li>原因 3：比较复杂度。 你代码中的 <code>if (cnt == key)</code> 对 <code>vector</code> 来说是线性遍历比较（26次迭代）。对 <code>unordered_map</code> 来说，<code>==</code> 操作符不仅要比较大小，还要逐个键查找值是否存在且相等，开销更大。</li></ul><blockquote>适用场景： 只有当字符集非常大且稀疏（比如万国码 Unicode，且只有少数几个字符出现）时，才考虑用 <code>unordered_map</code>。</blockquote><hr><ol start="2"><li>换成原生数组 <code>int[26]</code></li></ol>结论：性能最强，但代码灵活性降低。<ul><li>内存： 原生数组分配在栈上，省去了 <code>vector</code> 在堆上动态申请空间的开销（虽然本题只申请一次，影响较小）。</li><li>痛点：比较操作。 在 C++ 中，原生数组不能直接用 <code>==</code> 比较（<code>arr1 == arr2</code> 比较的是首地址指针）。<ul><li>你需要手动写一个循环比较 26 个位置。</li><li>或者使用 <code>memcmp(cnt, key, sizeof(cnt))</code>。</li></ul></li></ul><hr><ol start="3"><li>最优选：<code>std::array&lt;int, 26&gt;</code></li></ol>对于你的需求，如果你追求极致性能又想保留 <code>vector</code> 的方便，<code>std::array</code> 是完美选择。<pre><code class="lang-cpp">std::array&lt;int, 26&gt; cnt = {0}, key = {0};
// ... 逻辑不变 ...
if (cnt == key) { // std::array 支持直接用 == 比较，且效率极高
 ans.emplace_back(l);
}</code></pre><ul><li>优点： 它封装了原生数组，分配在栈上，大小固定。</li><li>效率： 它的 <code>operator==</code> 经过编译器优化，通常比 <code>vector</code> 的比较更快。</li></ul></blockquote>所以，灵神的题解用的是<code>array</code>，今天又学到了一点，哈哈。<h1>9-560 和为 K 的子数组</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：中等解题日期：2025.12.29标签：数组 哈希表 前缀和推荐题解：<a class="no-external-link" href="https://leetcode.cn/problems/subarray-sum-equals-k/solutions/2781031/qian-zhui-he-ha-xi-biao-cong-liang-ci-bi-4mwr/?envType=study-plan-v2&envId=top-100-liked" target="_blank">灵神对这道题的题解</a></blockquote>开头先把一句结论放在这里：这就是上面的"两数之和"的变种。讲讲我的思考心路历程吧。一开始看到这道题目，我的第一反应是用滑动窗口去做，毕竟上面刚刚做了滑窗的题目。但是疑问也随之而来：如果用定长滑窗，不就相当于暴力枚举，时间复杂度是O(n^2)；如果用不定长滑窗...用不了吧？毕竟数可能是负的，并不保证一定增长。所以，我打消了滑窗的念头。我想啊想，又想了5分钟，没想出来。Gemini曾经告诉我一个重要的道理：我现在的时间很宝贵，我的重点应该放在会做这道题目上，而不是一定要求自己做出来这道题目，过程不重要，重要的是结果。所以我就去看题解了。题解的思路一开始我还没看懂，继续丢给我这位AI老朋友，它成功给我教会了，来讲讲我的理解。首先，我们需要将一个区间和问题，利用老朋友前缀和转换成两个端点的问题。然后呢，从这里开始就和两数之和不太一样了：在两数之和，我们只需要找是否有和为k的两个数，但是在这里，我们需要返回数量。这就和之前不定长滑窗的思想有些类似了，我记得在滑窗的题单里我有接触过类似的题目：遍历到后面之后，看看前面有几个和自己匹配上的，将这里的数目累加进答案里即可。那么怎么计数呢？这里就需要用到哈希表了，我选择了<code>unordered_map</code>作为计数器。从前往后遍历数字，看看我要找的和这个数字对应的那个数字是否在计数器里，如果在就按照上面"匹配"的思路累加答案，然后无论在不在，都要把当前数字也累加进计数器，以便后面的数与它匹配。代码如下：<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
 int subarraySum(vector&lt;int&gt;&amp; nums, int k) {
 //1.先构建前缀和
 int n = nums.size();
 vector&lt;int&gt; prefixSum(n+1,0);
 for (int i=0;i&lt;n;i++) {
 prefixSum[i+1]=prefixSum[i]+nums[i];
 }
 //2.开始数数
 unordered_map&lt;int,int&gt; cnt;
 int ans = 0;
 for (int i=0;i&lt;=n;i++) {
 int target = prefixSum[i]-k;
 auto it = cnt.find(target);
 if (it!=cnt.end()) { //找到了
 ans+=it-&gt;second;
 }
 cnt[prefixSum[i]]++;
 }
 return ans;
 }
};</code></pre>这里有一点要注意，就是我用到了<code>find(key)</code>方法。如果是<code>C++20</code>，直接返回<code>bool</code>的<code>.contains(key)</code>方法更加方便(灵神题解用的就是这个方法)。那么为何不直接用<code>cnt[key]</code>判定存在性呢？因为：<blockquote>如果你调用 <code>cnt[key]</code>，而这个 <code>key</code> 不在 map 里，C++ 会自动创建一个该 key 的项，并赋予默认值（比如 0）。这会破坏哈希表的大小，甚至在逻辑判断上出错。而 <code>find</code> 不会修改哈希表。<code>find</code>的用法如下：返回值： 返回一个迭代器 (iterator)。查找成功： 迭代器指向该键值对。查找失败： 迭代器等于 <code>container.end()</code>。</blockquote>现在知道为啥要这么用的吧？顺带一提，这可能是我2025年的最后一道题目了，因为我还要抽时间写动态规划的算法笔记，最近期末复习也挺忙的。那么下一题，我们2026见！<h1>10-239 滑动窗口最大值</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/sliding-window-maximum/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/sliding-window-maximum/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：困难(Hard)解题日期：2026.1.6标签：队列 数组 滑动窗口 单调队列 堆（优先队列）推荐题解：<a class="no-external-link" href="https://leetcode.cn/problems/sliding-window-maximum/solutions/2499715/shi-pin-yi-ge-shi-pin-miao-dong-dan-diao-ezj6/?envType=study-plan-v2&envId=top-100-liked" target="_blank">灵神的题解，但是我没按照他的来</a></blockquote>现在是26年1月6日晚上21点37分，我在半小时前刚刚复习完概率论，想着最近这么忙，好几天没刷题了，正好今天有空，就来刷一下hot100吧。然后，按照惯例，我是会把所有困难题留在最后做的。但是这道题目不一样，我一点进来看题目，滑窗+优先队列的思路就冒出来了。挺顺，那就试着做做吧。但是我的第一反应是怀疑：Hard题怎么可能让我一眼看穿呢？于是我点开标签，看了一眼——还真有堆！(甚至都没看提示)然后我的第一版思路就冒出来了，直接调用我在灵神的滑窗题单里面修炼的炉火纯青的"删左加右"滑窗模型：把刚刚出窗户那个元素从<code>priority_queue&lt;int&gt; pq</code>里面删掉，然后把右边新进窗户的那个元素丢进去。想法是美好的，但是一问Gemini：优先队列不允许这样做，只能弹出堆顶元素。我的热情瞬间消减了一半，但是没有放弃。思索了一会，我想到了一个绝佳的思路，也就是我ac的代码的主要思路：继续用<code>pq</code>，但是是这样的<code>pq</code>：<code>priority_queue&lt;pair&lt;int,int&gt;&gt; pq</code>，在插入数的时候，把数放在<code>first</code>，把这个数的下标放在<code>second</code>。然后呢，左边出窗户的数我不管它，就让它在里面，然后正常把新进窗户的数丢进<code>pq</code>。然后在这里，我就要体现下标的作用了：开一个循环，判断堆顶元素的下标范围是否在我这个窗户里面，如果是，就说明是答案，我们正常取；否则就弹走，直到我堆顶元素的下标在窗户范围内。这个思路挺妙的，我们可以类比一下，把不同的窗户比作不同的部门：假设你是公司的老板，前一段时间公司进行了综合能力大比拼，每个人都被用相同的标准打了一个分。你现在只想要后端部门分数最高的那个人，那你就可以把全部人丢进堆里面，然后只需要盯着堆顶，如果堆顶的不是后端的，就弹走，如果是，那就说明这就是后端部门分数最高的了。这样为啥不会出错？因为堆是自动把堆里面分数最高的放在堆顶，由于一开始全部人都在里面，而后端部门的当然也全都在里面。那我就一直取堆顶呗，因为堆顶保证了堆顶元素一定是当前堆里面所有元素最大的，所以我取出的第一个后端的人的分数是全体堆元素最大的，那自然也能保证是后端部门分数最高的了。总结一下，这个思路就是看起来很乱，但是实际上挺巧的。我也挺好奇的，我为啥能突然想出来这个思路。那么，上代码！<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
 vector&lt;int&gt; maxSlidingWindow(vector&lt;int&gt;&amp; nums, int k) {
 priority_queue&lt;pair&lt;int,int&gt;&gt; pq;
 vector&lt;int&gt; ans;
 for (int l=0;l&lt;=nums.size()-k;l++) {
 if (l==0) { //初始化窗户内的数，便于后续&quot;删左增右&quot;
 for (int i=0;i&lt;k;i++) {
 pq.emplace(nums[i],i);
 }
 auto [value,_] = pq.top();
 ans.emplace_back(value);
 }else { //&quot;删左增右&quot;
 pq.emplace(nums[l+k-1],l+k-1); //增右
 int idx = pq.top().second; //取出下标
 while (!(idx&gt;=l &amp;&amp; idx&lt;l+k)) { //如果下标不在范围内，就弹出
 pq.pop();
 idx = pq.top().second;
 }
 //此时堆顶就是下标符合条件的最大值
 int value = pq.top().first;
 ans.emplace_back(value);
 }
 }
 return ans;
 }
};</code></pre>当然，这题的正统做法还是得讲讲：单调队列。直接看Gemini生成的吧，或者看上面的灵神题解版本也可以：<blockquote>进阶：$O(n)$ 做法 —— 单调队列 (Monotonic Queue)虽然优先队列（堆）的 $O(n \log n)$ 已经足够通过此题，但利用单调队列可以将时间复杂度进一步优化至极致的 $O(n)$。<ol><li>核心思想：删除“冗余”元素</li></ol>在一个窗口内，如果 $i &lt; j$ 且 $nums[i] \leq nums[j]$，那么只要 $nums[j]$ 还在窗口里，$nums[i]$ 就永远不可能成为最大值。<ul><li>$nums[j]$ 比 $nums[i]$ 更大。</li><li>$nums[j]$ 比 $nums[i]$ 在窗口里停留的时间更长（更晚过期）。因此，$nums[i]$ 就是“冗余”的，可以直接丢弃。</li></ul><ol start="2"><li>算法流程</li></ol>使用 <code>std::deque</code>（双端队列）维护一个下标序列，并保持队列对应的元素值严格单调递减：<ol><li>入队：当新元素 <code>nums[i]</code> 进入时，从队尾弹出所有小于等于它的元素（因为它们冗余了）。</li><li>出队（维护窗口）：检查队头下标是否已超出窗口范围（即 <code>dq.front() == i - k</code>），若是则弹出。</li><li>取最值：此时队头下标对应的元素即为当前窗口的最大值。</li><li>代码实现</li></ol><pre><code class="lang-cpp">vector&lt;int&gt; maxSlidingWindow(vector&lt;int&gt;&amp; nums, int k) {
 deque&lt;int&gt; dq; // 存储下标
 vector&lt;int&gt; ans;
 for (int i = 0; i &lt; nums.size(); ++i) {
 // 1. 保证单调递减：剔除队尾所有比当前元素小的“冗余”者
 while (!dq.empty() &amp;&amp; nums[dq.back()] &lt;= nums[i]) {
 dq.pop_back();
 }
 dq.push_back(i);
 
 // 2. 保证窗口合法：弹出过期的队头
 if (dq.front() == i - k) {
 dq.pop_front();
 }
 
 // 3. 记录答案：窗口形成（i &gt;= k-1）后开始收集
 if (i &gt;= k - 1) {
 ans.push_back(nums[dq.front()]);
 }
 }
 return ans;
}</code></pre><ol start="4"><li>复杂度对比</li></ol><table><thead><tr><th>算法</th><th>时间复杂度</th><th>空间复杂度</th><th>备注</th></tr></thead><tbody><tr><td>优先队列（延迟删除）</td><td>$O(n \log n)$</td><td>$O(n)$</td><td>简单直观，依赖堆的自动排序</td></tr><tr><td>单调队列</td><td>$O(n)$</td><td>$O(k)$</td><td>极致优化，每个元素仅入队/出队一次</td></tr></tbody></table></blockquote>好的，那就讲到这里。<h1>11-76 最小覆盖子串</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/minimum-window-substring/description/?envType=study-plan-v2&envId=top-100-likedd" target="_blank">https://leetcode.cn/problems/minimum-window-substring/description/?envType=study-plan-v2&envId=top-100-likedd</a>难度：困难(Hard)解题日期：2026.1.7标签：哈希表 字符串 滑动窗口推荐题解：<a class="no-external-link" href="https://leetcode.cn/problems/minimum-window-substring/solutions/2713911/liang-chong-fang-fa-cong-o52mn-dao-omnfu-3ezz/?envType=study-plan-v2&envId=top-100-liked" target="_blank">灵神的题解</a></blockquote>这题的做题经历可谓是一波三折。我之前是做过这个题的，在我刷滑窗题单的时候，用Go过的。结果，今天我用类似的思路，用cpp过的时候，直接给我干超出内存限制了？？？我是第一次见这个错误。<img src="https://dl2.lecspace.com/LositaBlog/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0/hot100-76-%E6%8F%90%E4%BA%A4%E6%83%85%E5%86%B5.png" alt="提交情况" title="提交情况" style="">后面问了Gemini才破案：我代码里面的<code>s.substr</code>发力了。先讲讲我的思路吧，和我在上次第一次做这道题目的思路是一样的：使用"右指针一直往右，直到符合条件，再将左指针往右，将窗户收缩到不符合条件为止，即得最短的符合长度子串"的滑窗模型，如果忘记了，可以去<a href="https://blog.lecspace.com/index.php/archives/76/">我的笔记</a>看看。然后呢，在符合条件的时候，我就习惯性直接像Go,python的字符串切片一样，用<code>s.substr(l,r-l+1)</code>把这个字符串直接切进我准备<code>return</code>的<code>ans</code>字符串里面去了。由于这个操作是会复制子串的，在用例比较大的时候就会爆内存。知道原因之后，解决方法也很简单：新起两个变量，用于存储最短符合条件状态下的子串的起点和终点下标，最后返回之前再看情况动用<code>substr</code>来切取子串。这样问题就解决了。看代码：<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
 bool isCovered(unordered_map&lt;char,int&gt; &amp;cntT,unordered_map&lt;char,int&gt; &amp;cntS) {
 for (auto [k,v]:cntT) {
 if (cntS.count(k)==0 || cntS[k]&lt;v) return false;
 }
 return true;
 }
 string minWindow(string s, string t) {
 if (s.size()&lt;t.size()) return &quot;&quot;;
 //1.先统计t里面各个数的情况
 unordered_map&lt;char,int&gt; cntT,cntS;
 for (auto &amp;x:t) {
 cntT[x]++;
 }
 //2.开始滑窗
 int l=0,minLength=s.size()+1,minL=-1,minR=s.size()+1;
 string ans=&quot;&quot;;
 for (int r=0;r&lt;s.size();r++) {
 cntS[s[r]]++;
 while (isCovered(cntT,cntS)) {
 if (r-l+1&lt;minLength) {
 minL=l;
 minR=r;
 minLength = r-l+1;
 }
 cntS[s[l]]--;
 l++;
 }
 }
 if (minL==-1) return &quot;&quot;;
 ans = s.substr(minL,minR-minL+1);
 return ans;
 }
};</code></pre>当然，这个<code>isCovered()</code>函数是可以优化成O(1)的，不过我懒得弄，5%极限过测就完事了，哈哈。就讲到这里。<h1>12-56 合并区间</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：中等解题日期：2026.1.8标签：数组 排序推荐题解：<a class="no-external-link" href="https://leetcode.cn/problems/merge-intervals/solutions/2798138/jian-dan-zuo-fa-yi-ji-wei-shi-yao-yao-zh-f2b3/?envType=study-plan-v2&envId=top-100-liked" target="_blank">灵神的题解</a></blockquote>这道题还是挺有意思的，让我找回了久违的"打补丁"感觉。先讲讲我一开始的思路吧。首先，我想到了把区间按照左端点升序排序。这是我刷题这么久的感觉告诉我的。然后后面，由于这是数组分类的题目，没有任何固定算法思想可循，我就开了个循环，开完循环之后一边写一边想：<ol><li>第一版思路：如果后面那个区间的左端点&lt;=现在这个区间的右端点，就说明两个区间交叉在一起了，这时候，就直接取后面这个区间的右端点为即将加入答案集合的右端点。</li><li>第二版思路：但是上面那版思路会有些问题：如果当前区间把后面那个区间包裹住了，这样做会使得区间缩小，导致后面全错。于是我又引入了<code>max()</code>函数。发现自己忘记处理没交叉的情况了，给没交叉的情况补上。</li><li>第三版思路：但是上面那版思路会有些问题：如果当前区间把后面那个区间包裹住了，这样做会使得区间缩小，导致后面全错。于是我又引入了<code>max()</code>函数。</li></ol>经过三次迭代，三次打补丁，我终于ac了！看代码：<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
 vector&lt;vector&lt;int&gt;&gt; merge(vector&lt;vector&lt;int&gt;&gt;&amp; intervals) {
 //1.排序
 sort(intervals.begin(), intervals.end(),[](auto a,auto b) {
 return a[0]&lt;b[0];
 });
 //2.开始拼接
 int n = intervals.size(),tempL=0,tempR=0;
 vector&lt;vector&lt;int&gt;&gt; ans;
 for (int i=0;i&lt;n;i++) {
 if (i&lt;n-1 &amp;&amp; intervals[i][1]&gt;=intervals[i+1][0]) {
 tempL=intervals[i][0];
 tempR=intervals[i][1];
 while (i&lt;n-1 &amp;&amp; (intervals[i][1]&gt;=intervals[i+1][0] || intervals[i+1][0]&lt;=tempR)) {
 tempR=max(tempR,intervals[i+1][1]);
 i++;
 }
 ans.emplace_back(vector&lt;int&gt;{tempL,tempR});
 } else {
 ans.emplace_back(intervals[i]);
 }
 }
 return ans;
 }
};</code></pre>我自己也感觉这样不是个办法，冥冥之中，我感觉这道题目肯定有更简单的做法。于是我问了Gemini，看了它的思路，我秒懂。它一句话点醒了我：<blockquote>你之所以觉得思路乱，是因为你的代码试图在遍历的过程中“向前看”（观察 <code>i+1</code>）并且手动维护了一个内部 <code>while</code> 循环来跨越多个重叠区间。这种写法逻辑分支多，容易在边界条件（比如最后一个元素、嵌套区间）上出错，所以你才需要通过“打补丁”来 AC。其实，处理这类问题有一个更优雅、更通用的思路：“向后看”。</blockquote>那么具体如何向后看呢？就是：正常往后遍历，把第一个区间丢进<code>ans</code>之后，盯着<code>ans</code>的最后一个区间看。我们分两种情况处理：<ol><li>如果现在的这个区间的左端点比最后一个区间的右端点大，那说明一定接不上，直接给这个区间丢进去，让它成为<code>ans</code>的最后一个区间。</li><li>如果现在这个区间的左端点比最后一个区间的右端点小，说明是可以接上的。至于如何更新最后一个区间的右端点？依旧取<code>max(ans.back()[1],cur[1]);</code>。</li></ol>上代码吧，比我之前的思路少了不知道多少。<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
 vector&lt;vector&lt;int&gt;&gt; merge(vector&lt;vector&lt;int&gt;&gt;&amp; intervals) {
 //1.排序
 sort(intervals.begin(), intervals.end(),[](auto a,auto b) {
 return a[0]&lt;b[0];
 });
 //2.开始拼接
 int n = intervals.size();
 vector&lt;vector&lt;int&gt;&gt; ans;
 for (auto &amp;x:intervals) {
 if (ans.empty() || x[0]&gt;ans.back()[1]) {
 ans.emplace_back(x);
 }else {
 ans.back()[1] = max(ans.back()[1],x[1]);
 }
 }
 return ans;
 }
};</code></pre>真的挺神奇的，又学到了新知识。玩一下抽象：其实人生也是一样，有的时候我们只顾着向前看，其实有时候向后看，吸取教训，会比向前看更有收获。<del>(硬扯这块)</del><h1>13-189 轮转数组</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/rotate-array/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/rotate-array/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：中等解题日期：2026.1.9标签：数组 数学 双指针推荐题解：<a class="no-external-link" href="https://leetcode.cn/problems/rotate-array/solutions/2784427/tu-jie-yuan-di-zuo-fa-yi-tu-miao-dong-py-ryfv/?envType=study-plan-v2&envId=top-100-liked" target="_blank">灵神的题解</a></blockquote>这应该是目前我做Hot100做到过最抽象的题目了。这题如果使用额外空间，非常简单：先把轮换的次数k对着数组长度取个余，防止题目故意用超出长度的轮换次数坑你；然后再根据k，切片数组的后k个元素到新的数组，然后再删掉原数组的后k个元素，然后再将新数组和原数组直接拼接。如果用Python，代码4行就搞定了：取余，切片并赋值，切片并赋值，拼接并赋值。就像这样：<pre><code class="lang-python">class Solution:
 def rotate(self, nums: List[int], k: int) -&gt; None:
 k%=len(nums)
 s1=nums[len(nums)-k:]
 s2=nums[:len(nums)-k]
 nums[:]=s1+s2 #对，由于我好久没写Python了，这里需要加[:]才能真正修改nums，属于是被迫补齐Python知识了(</code></pre>用cpp也同理，这里突然用python主要是因为python的切片算是我接触过的语言里面最无脑最直观的了。那么如何不用额外空间来完成这道题呢？我没啥头绪，就打开标签看了一眼，当我看到那两个字的时候，我已经来不及了：双指针。这我怎么会写？于是我直接打开了题解，看到了灵神的思路：负负得正。真的挺牛的。大致思路是这样的：由于轮换k次就是给后k个数挪到前面，那我直接把整个数组倒过来，后k个数就占据了前k个位置。然后我再把位置是前k个数的那些数给倒回去，再把剩下的另一个子数组的数也倒回去，就完成了k次轮换。代码量少、思路简单的同时，不会占据任何额外空间(至少cpp的<code>reverse()</code>是这样的)。直接上代码：<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
 void rotate(vector&lt;int&gt;&amp; nums, int k) {
 k%=nums.size();
 reverse(nums.begin(), nums.end());
 reverse(nums.begin(),nums.begin()+k);
 reverse(nums.begin()+k,nums.end());
 }
};</code></pre>这题真的挺神金的，大晚上逗我笑一下，哈哈。<h1>14-238 除了自身以外数组的乘积</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：中等解题日期：2026.1.18标签：数组 前缀和推荐题解：<a class="no-external-link" href="https://leetcode.cn/problems/product-of-array-except-self/solutions/2783788/qian-hou-zhui-fen-jie-fu-ti-dan-pythonja-86r1/?envType=study-plan-v2&envId=top-100-liked" target="_blank">灵神的题解</a></blockquote>别问我为啥9天没刷题——你知道我这9天是怎么过的吗？？？11号上午毛概，13号晚上习概，14号下午c++，15号下午数电，然后后面20号还有概率论，21号离散数学，22号数据结构。也就是说，我刚刚从1+3连考的地狱中爬出来，刚刚喘息了2天，后面就要继续迎接3连考，才能放假。我*。回归正题。这题说来也好笑，由于我急着回宿舍，没看到题目要求的 不要使用除法，直接上了欧美做法，倒是没使用额外空间，看代码：<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
 vector&lt;int&gt; productExceptSelf(vector&lt;int&gt;&amp; nums) {
 //1.先计算总乘积
 ll all=1;
 int zeroCnt=0;
 for (auto&amp; x:nums) {
 if (x==0) {
 zeroCnt++;
 }else {
 all*=x;
 }
 }
 //2.再算目标数组
 vector&lt;int&gt; ans;
 for (auto&amp; x:nums) {
 if (x==0) {
 if (zeroCnt&lt;=1) ans.emplace_back(all);
 else ans.emplace_back(0);
 }else {
 if (zeroCnt&gt;0) ans.emplace_back(0);
 else ans.emplace_back(all/x);
 }
 }
 return ans;
 }
};</code></pre>具体做法就不解释了，没套任何算法模型，就是利用了"总乘积/当前元素"得到答案，这是题目禁止的做法。这道题的正解也不难，其实就是左前缀乘积和+右后缀乘积和，将这两个前缀后缀乘积和预处理好，就可以O(1)时间复杂度获取到当前位置元素的前面元素的乘积和后面元素的乘积，将二者一乘就是答案，没使用除法。看代码：<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
 vector&lt;int&gt; productExceptSelf(vector&lt;int&gt;&amp; nums) {
 //1.先计算前后缀乘积数组
 int n=nums.size();
 vector&lt;int&gt; pre(n),suf(n);
 for (int i=0;i&lt;n;i++) {
 if (i==0) {
 pre[0]=1;
 }else {
 pre[i]=pre[i-1]*nums[i-1];
 }
 }
 for (int i=n-1;i&gt;=0;i--) {
 if (i==n-1) {
 suf[i]=1;
 }else {
 suf[i]=suf[i+1]*nums[i+1];
 }
 }
 //2.直接出结果
 vector&lt;int&gt; ans(n);
 for (int i=0;i&lt;n;i++) {
 ans[i]=suf[i]*pre[i];
 }
 return ans;
 }
};</code></pre>这题难度不高，我觉得如果去掉禁止用除法这个条件，难度可以改成简单。<h1>15-41 缺失的第一个正数</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/first-missing-positive/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/first-missing-positive/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：Hard(困难)解题日期：2026.1.19标签：数组 哈希表推荐题解：<a class="no-external-link" href="https://leetcode.cn/problems/first-missing-positive/solutions/3655377/huan-zuo-wei-tong-guo-li-zi-li-jie-suan-qa94e/?envType=study-plan-v2&envId=top-100-liked" target="_blank">灵神的题解，先看，再配合我下面的补充就很清楚了</a></blockquote>今天也是继续欧美，直接来上手Hard题——不过这次的运气就没这么好了，不但没想出来，而且看题解也理解了半天，可算是弄懂了。可以先看题目，再看上方的灵神题解，看完灵神题解之后，再往下看。这道题目的思路，其实和"打补丁"特别像——我们先形成初步思路，然后再一步步完善：<ol><li>首先，我们会想着给这些元素"排座位"，也是下面所有解法的目的：那些不是正整数的数我们不管，我们需要做的，是尝试把每个正整数都放到和下标相对应的位置。由于这道题目的<code>nums</code>是0base，所以我们需要尝试让<code>nums[i]==i+1</code>。在我安排完所有数之后，再遍历一遍数组，发现的第一个"无家可归"的数，它所在的位置+1就是缺失的第一个正数。</li><li>那么如何高效的把每个元素放到正确的位置上呢？并且还要求原地操作。有两种思路，都是遍历数组：第一种是直接暴力搜索"这个位置属于哪个数"，外层循环遍历位置，内存循环找数，时间复杂度妥妥的O(n^2)，肯定不行；第二种是正常遍历，"如果这个数不属于这个位置，就把这个数送到它该去的地方"。那第二种方法是不是就不需要新开一层循环了呢？还是需要的，因为我们没法保证换过来的那个数就一定属于现在的这个位置。所以我们需要开个循环，把换过来的、不属于这个位置的数继续送到它该去的位置上。至于时间复杂度呢？由于我们每次"送数"都会让一个数去到它该去的地方，看似双重循环，实则我的内层循环跑一次就能解决1个位置问题，总共有最多n个位置问题等待我解决，那么相当于还是O(n)。</li><li>那么我们需要好好思考一下这个循环的条件了。首先，我"送数"的前提，肯定是这个数和当前位置不匹配，那么就需要判断一下是否匹配。其次，我们可能会遇到越界的数，例如比1小，比n大的数，这种数是无家可归的，所以我们不需要动它，只需要等待后续可能有属于该位置的数把这个无家可归的数换走，让它继续"流浪"。初步的循环条件就是这样的：<code>nums[i]&gt;=1 &amp;&amp; nums[i]&lt;=n &amp;&amp; nums[i]!=i+1</code>。</li><li>但是这样有个问题：如果遇到重复的数怎么办？这也是灵神题解里面最难理解的"影分身"部分。举个例子吧，假设我当前位置<code>i=1</code>，这里的数是3，而<code>i=2</code>的位置上的数也是3。如果按照上面的循环条件，它会把这两个一模一样的3交换一次，并且交换完之后，循环条件还是成立！这样就会陷入死循环。</li><li>此时，就体现了我说的"打补丁"思想了。我们只需要判断：如果当前这个数不匹配该位置，并且它的目标位置已经有和它一模一样的数了，就说明触发了这种重复的情况，我们为了避免死循环，就只能退出循环，不交换。于是我们增加条件：<code>nums[i]!=nums[nums[i]-1]</code>。这就相当于打补丁，修复了一个死循环的bug。</li><li>然后，按照这个逻辑，我们就能跑完对数组的第一遍遍历。至于第二遍的事情就很简单了，只需要找第一个不匹配的下标就行。如果全都匹配，说明这些数贴的很紧，没有空隙，那么缺失的第一个(也就是最小的)正数就是<code>n+1</code>。</li><li>至此，思路完毕。</li></ol>讲的已经很清楚了，上代码：<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
 int firstMissingPositive(vector&lt;int&gt;&amp; nums) {
 //1.第一次遍历
 int n = nums.size();
 for (int i=0;i&lt;n;i++) {
 while (nums[i]&gt;=1 &amp;&amp; nums[i]&lt;=n &amp;&amp; nums[i]!=i+1 &amp;&amp; nums[i]!=nums[nums[i]-1]) {
 int j = nums[i]-1;
 swap(nums[i],nums[j]);
 }
 }
 //2.第二次遍历
 for (int i=0;i&lt;n;i++) {
 if (nums[i]!=i+1) {
 return i+1;
 }
 }
 return n+1;
 }
};</code></pre>然后呢，其实有一个优化的点：这个<code>nums[i]!=i+1</code>条件其实是可以删掉的——它已经被后面那个用来检测是否重复的条件覆盖掉了。我们推理一下：当<code>nums[i]==i+1</code>时，将<code>nums[i]=i+1</code>代入后者，可以得到<code>nums[nums[i]-1]=nums[(i+1)-1]=nums[i]</code>，也就是前面如果成立，后面也成立。反之，前面如果不成立，那后面肯定也不成立。所以，从数学的角度，我们把前者吸收掉了。好的，就写这么多，这道题目还是挺有挑战性的。<h1>16-73 矩阵置零</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/set-matrix-zeroes/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/set-matrix-zeroes/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：中等解题日期：2026.1.26标签：数组 哈希表 矩阵推荐题解：<a class="no-external-link" href="https://leetcode.cn/problems/set-matrix-zeroes/solutions/3799648/yi-bu-bu-you-hua-cong-omn-dao-o1-kong-ji-fdgt/?envType=study-plan-v2&envId=top-100-liked" target="_blank">灵神的题解</a></blockquote>好多天不见！这几天我经历了概率论-离散数学-数据结构三连考，并且还跨越了1700km，才回到了家。今天我缓过来了，于是我又来做算法了。回归正题。这道题要求我们使用原地算法来解决问题，我一开始还是比较茫然的(当然暴力的方法肯定是秒出，主要是巧方法没想出来)，一看提示，一下子就会了：将矩阵的第一行和第一列作为记录信息的地方，记录它们各自元素所处的列/行是否有0。但是一开始我想偏了，以为是要把这个矩阵从0base改成1base(这样很自然空出来了一个行和一个列)，然后又难以下手(既不想复制，又不知道怎么直接优雅的加上去)。于是，我就灵机一动，把这个第一行和第一列单独提出来了。代码如下：<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;

class Solution {
public:
 void setZeroes(vector&lt;vector&lt;int&gt;&gt;&amp; matrix) {
 //1.设置flags
 int n = matrix.size(),m = matrix[0].size();
 vector&lt;bool&gt; xFlags(n,false),yFlags(m,false);
 //2.探测有0的列
 for (int i=0;i&lt;n;i++) {
 for (int j=0;j&lt;m;j++) {
 if (matrix[i][j]==0) {
 xFlags[i]=true;
 yFlags[j]=true;
 }
 }
 }
 //3.改0
 for (int i=0;i&lt;n;i++) {
 for (int j=0;j&lt;m;j++) {
 if (xFlags[i] || yFlags[j]) matrix[i][j]=0;
 }
 }
 }
};</code></pre>然后，ac，很丝滑。一问AI，AI说我符合题目的原地要求，并且处于进阶的第二阶段(一个简单的改进方案是使用 <code>O(m + n)</code> 的额外空间，但这仍然不是最好的解决方案。于是我就向它学习了一下如何只使用常量空间，这下看懂了：<ol><li>准备两个变量，用来记录第一行第一列本身是否有0。然后分别扫描第一行第一列，根据是否有0的实际情况来更改这两个变量的值。</li><li>再和上面代码一样开始遍历这个矩阵(从(1,1)开始)，如果遇到0，就给第一行和第一列的对应位置置0。</li><li>最后也和上面一样，但是还是从(1,1)开始处理，如果第一行或者第一列的对应位置是0，就给当前元素置零。</li><li>结束之后，还得单独处理第一行和第一列。根据变量的值判断是否需要单独给它们本身置零，然后操作。</li><li>最后，为何需要单独准备两个变量呢？就举个极端例子吧。假设第一行全都是1，然后某一列的元素有0，就会把第一行的对应位置置0，这时候，我们就没法判断这个0是第一行本来就有的，还是被下面的0给改变出来的，就没法判断是否要给第一行本身清零。有了这两个变量之后，我们就只看这两个变量决定要不要清零，这样结果才是准确的。</li></ol>上代码：<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;

class Solution {
public:
 void setZeroes(vector&lt;vector&lt;int&gt;&gt;&amp; matrix) {
 //1.探测第一行第一列是否有0
 bool xZero=false,yZero=false;
 int n = matrix.size(),m = matrix[0].size();
 for (int i=0;i&lt;m;i++) {
 if (matrix[0][i]==0) {
 xZero = true;
 break;
 }
 }
 for (int i=0;i&lt;n;i++) {
 if (matrix[i][0]==0) {
 yZero=true;
 break;
 }
 }
 //2.开始检测
 for (int i=1;i&lt;n;i++) {
 for (int j=1;j&lt;m;j++) {
 if (matrix[i][j]==0) {
 matrix[i][0]=0;
 matrix[0][j]=0;
 }
 }
 }
 //3.开始置零
 for (int i=1;i&lt;n;i++) {
 for (int j=1;j&lt;m;j++) {
 if (matrix[0][j]==0 || matrix[i][0]==0) matrix[i][j]=0;
 }
 }
 //4.最后处理第一行列
 if (xZero) {
 for (int i=0;i&lt;m;i++) {
 matrix[0][i]=0;
 }
 }
 if (yZero) {
 for (int i=0;i&lt;n;i++) {
 matrix[i][0]=0;
 }
 }
 }
};</code></pre>就讲到这里。<h1>17-54 螺旋矩阵</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/spiral-matrix/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/spiral-matrix/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：中等解题日期：2026.1.26标签：数组 矩阵 模拟推荐题解：<a class="no-external-link" href="https://leetcode.cn/problems/spiral-matrix/solutions/2966229/liang-chong-fang-fa-jian-ji-gao-xiao-pyt-4wzk/?envType=study-plan-v2&envId=top-100-liked" target="_blank">灵神的题解</a></blockquote>这道题目也算是比较经典的模拟题目了。方法百花齐放，基本上都是找规律。我找的规律是这样的：观察到螺旋矩阵输出时的行进方向为右-&gt;下-&gt;左-&gt;上的循环，于是就新建了两个分别负责x和y的方向数组，并且用一个指针来循环选择这四个方向。换方向的条件是这样的：如果按照当前方向行进，下标越界或者前方元素已经访问过，就说明我们需要转变方向了，就将这个指针循环+1，然后再判断一下+1后符不符合条件，如果按照新方向行进还是不符合条件，那就说明进入了死胡同，即全部元素都遍历完了。上代码：<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
 vector&lt;int&gt; spiralOrder(vector&lt;vector&lt;int&gt;&gt;&amp; matrix) {
 vector&lt;int&gt; dx = {0,1,0,-1};
 vector&lt;int&gt; dy = {1,0,-1,0};
 vector&lt;int&gt; ans;
 int p=0,x=0,y=0;
 int n = matrix.size(),m = matrix[0].size();
 vector&lt;vector&lt;bool&gt;&gt; visited(n,vector&lt;bool&gt;(m,false));
 while (true) {
 ans.emplace_back(matrix[x][y]);
 visited[x][y]=true;
 if (x+dx[p]&lt;0 || x+dx[p]&gt;=n || y+dy[p]&lt;0 || y+dy[p]&gt;=m || visited[x+dx[p]][y+dy[p]]) {
 p=(p+1)%4;
 if (x+dx[p]&lt;0 || x+dx[p]&gt;=n || y+dy[p]&lt;0 || y+dy[p]&gt;=m || visited[x+dx[p]][y+dy[p]]) break;
 }
 x+=dx[p];
 y+=dy[p];
 }
 return ans;
 }
};</code></pre>当然，我的代码还是有优化空间的，可以将额外空间的这个visited矩阵改成边界的收缩，亦或是直接在原矩阵上标记，都可以将空间复杂度降低到O(1)。由于比较简单，就不再赘述。<h1>18-48 旋转图像</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/rotate-image/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/rotate-image/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：中等解题日期：2026.1.27标签：数组 数学 矩阵推荐题解：<a class="no-external-link" href="https://leetcode.cn/problems/rotate-image/solutions/3655166/shu-xue-ben-zhi-liang-ci-fan-zhuan-deng-aon4a/?envType=study-plan-v2&envId=top-100-liked" target="_blank">灵神的题解</a></blockquote>这道题就比较有意思了，同样也是找规律。我们观察示例里面元素的位置变化，假设每个元素的坐标为(i,j)，很容易发现每个元素从(i,j)变到了(j,n-1-i)。这里我是偷懒了，所以直接写了我发现的结论。如果难以发现规律，可以先看x轴坐标变化，再看y轴坐标变化，就和上方题解一样，慢慢来，会好一些。知道了每个坐标的变化规律之后，就好办了...吗？我们需要原地变换数组，如果新开一个数组当然简单，无脑一直按照上面的规律取就行了。我们只能原地变换，注定我们只能交换两个元素(使用<code>std::swap()</code>)，而直接交换是行不通的。这时候就来到了这道题的核心：将上面的变化规律拆成两步边界分明的变化，变成<code>(i,j)-&gt;(j,i)-&gt;(j,n-1-i)</code>。为啥要边界分明呢？我们需要保证我们的交换操作在每一对元素身上只会被进行一次，不会出现被换过去的元素被换回来的情况。你看第一步，属于矩阵的斜对称，边界很明确，就是(i,i)这条斜线，这样我们在操作的时候，就能用循环很好的限定操作范围为矩阵的上三角。第二步就更简单了，属于矩阵的左右对称(x轴不变，只变y轴)，边界也很分明，是矩阵的中线。不过找这根线还是有难度，我列了好几个式子才发现它是<code>matrix.size()/2-1</code>。至此，思路毕。上代码：<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
 void rotate(vector&lt;vector&lt;int&gt;&gt;&amp; matrix) {
 //(i,j)-&gt;(j,i)-&gt;(j,n-1-i)
 int m = matrix.size();
 //1. (i,j)-&gt;(j,i)
 for (int i=0;i&lt;m;i++) {
 for (int j=i;j&lt;m;j++) {
 swap(matrix[i][j],matrix[j][i]);
 }
 }
 //2.(j,i)-&gt;(j,n-1-i)
 for (int i=0;i&lt;m;i++) {
 for (int j=0;j&lt;=m/2-1;j++) {
 swap(matrix[i][j],matrix[i][m-1-j]);
 }
 }
 }
};</code></pre>就讲到这里。<h1>19-240 搜索二维矩阵 II</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/search-a-2d-matrix-ii/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/search-a-2d-matrix-ii/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：中等解题日期：2026.1.27标签：数组 二分查找 分治 矩阵推荐题解：<a class="no-external-link" href="https://leetcode.cn/problems/search-a-2d-matrix-ii/solutions/2783938/tu-jie-pai-chu-fa-yi-tu-miao-dong-python-kytg/?envType=study-plan-v2&envId=top-100-liked" target="_blank">灵神的题解</a></blockquote>这题就和前面的题目有些不一样了，单纯找规律可能很难找到解法。我甚至看了两遍题解才真正理解这题做法的关键所在。看完第一遍题解，我领悟到了"收缩边界"和"分治"两个概念，在代码的开头定义了四个变量来圈定边界，甚至还在思考要不要用递归、边界条件怎么判断，如何退出...挺麻烦的。于是我看了第二遍题解，才抓到这个做法的核心：只盯着右上角看，然后只收缩x轴的下界和y轴的上界。且听我娓娓道来。首先，这个矩阵具有这样的特性：<ul><li>每行的元素从左到右升序排列。</li><li>每列的元素从上到下升序排列。</li></ul>这就说明，如果某一列的第一个元素比我的目标元素大，那这一列一定没有我的目标元素，可以直接排除；同理，如果某一行的最后一个元素比我的目标元素小，那这一行也可以直接排除。在这个做法里面，我们只盯着右上角的元素。按照上面的说法，如果这个元素比我的目标元素大，那就把右上角元素所在这一列排掉，y轴上界(数值高的那一边)减一，相当于往左边收缩一格；如果和目标相等，那就是找到了；如果比我的目标元素小，那就把右上角元素所在这一行排掉，x轴下界(数值低的那一边)加一，相当于往下面收缩一格。如此往复，直到右上角元素就是目标元素。如果边界收缩的越界了还没找到，那说明没找到，退出循环。代码如下：<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
 bool searchMatrix(vector&lt;vector&lt;int&gt;&gt;&amp; matrix, int target) {
 int n=matrix.size(),m=matrix[0].size(),xl=0,xh=n-1,yl=0,yh=m-1;
 while (xh&gt;=xl &amp;&amp; yh&gt;=yl) {
 int upRight = matrix[xl][yh];
 if (upRight&gt;target) {
 yh--;
 }else if (upRight==target) {
 return true;
 }else {
 xl++;
 }
 }
 return false;
 }
};</code></pre>顺带一提，为了方便寻找右上角的坐标，我的边界是设置为包含其本身的，也就是闭区间。这个只盯着右上角的做法还是很巧妙的，把我看完题解第一遍的那些麻烦的边界判断想法全都免去了。<h1>20-160 相交链表</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/search-a-2d-matrix-ii/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/search-a-2d-matrix-ii/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：简单解题日期：2026.1.28标签：哈希表 链表 双指针推荐题解：<a class="no-external-link" href="https://leetcode.cn/problems/intersection-of-two-linked-lists/solutions/2958778/tu-jie-yi-zhang-tu-miao-dong-xiang-jiao-m6tg1/?envType=study-plan-v2&envId=top-100-liked" target="_blank">灵神的题解</a></blockquote>既然这题是简单题，那我们长话短说。题解都看完了吧？首先，我想到的是<a class="no-external-link" href="https://leetcode.cn/problems/intersection-of-two-linked-lists/solutions/811625/xiang-jiao-lian-biao-by-leetcode-solutio-a8jn/?envType=study-plan-v2&envId=top-100-liked" target="_blank">官方题解</a>里面的第一种方法：哈希法，就是把链表A每个节点的指针都丢进无序集合里面，在遍历链表B的时候不断检查当前节点是否在这个集合里面(时间复杂度O(1))，第一个被检查出存在的节点就是两个链表相交的地方。顺带一提，cpp的指针之间的比较比的是地址，和节点的值没有关系。这也是这个做法能不受题目中数字干扰的重要原因。代码如下：<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

struct ListNode {
    int val;
    ListNode *next;

ListNode(int x) : val(x), next(NULL) {
    }
};

class Solution {
public:
 ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
 unordered_set&lt;ListNode*&gt; hash;
 ListNode* p = headA;
 while (p) {
 hash.emplace(p);
 p=p-&gt;next;
 }
 p=headB;
 while (p) {
 if (hash.count(p)) {
 return p;
 }
 p=p-&gt;next;
 }
 return nullptr;
 }
};</code></pre>但是这个方法还是需要O(n)的额外空间，太吃内存了。那么我们该如何把它优化到O(1)的额外空间呢？答案就是双指针。也就是官方题解的方法2和灵神题解的方法。这个方法其实挺浪漫的，就是：如果你走过我走过的路，我走过你走过的路，我们终会相遇。不扯浪漫，数学原理其实也简单：<ol><li>指针 <code>pA</code> 从 <code>headA</code> 开始走，指针 <code>pB</code> 从 <code>headB</code> 开始走。</li><li>当 <code>pA</code> 走到 <code>headA</code> 的末尾时，让它转场到 <code>headB</code> 的开头继续走。</li><li>当 <code>pB</code> 走到 <code>headB</code> 的末尾时，让它转场到 <code>headA</code> 的开头继续走。</li><li>奇迹时刻： 两个指针会在相交节点处相遇。</li></ol>为什么？假设 A 链表非相交部分长 a，B 链表非相交部分长 b，相交部分长 c。<ul><li>指针 <code>pA</code> 走的距离：a + c (走完 A) + b (开始走 B 的非相交部分)</li><li>指针 <code>pB</code> 走的距离：b+c (走完 B) + a (开始走 A 的非相交部分)</li><li>结果： a + c + b = b + c + a。两者走的长度相等，刚好在相交点碰头！</li></ul>当然，写的时候要注意，ab需要同时移动，就是你走一步我也走一步，即放在同个循环里面。代码如下：<pre><code class="lang-cpp">class Solution {
public:
 ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
 ListNode *pA,*pB;
 pA=headA;pB=headB;
 while (pA!=pB) {
 if (pA) pA=pA-&gt;next;
 else pA=headB;
 if (pB) pB=pB-&gt;next;
 else pB=headA;
 }
 return pA;
 }
};</code></pre>就讲到这里。<h1>21-206 反转链表</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/reverse-linked-list/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/reverse-linked-list/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：简单解题日期：2026.1.28标签：递归 链表推荐题解：<a class="no-external-link" href="https://leetcode.cn/problems/reverse-linked-list/solutions/1992225/you-xie-cuo-liao-yi-ge-shi-pin-jiang-tou-o5zy/?envType=study-plan-v2&envId=top-100-liked" target="_blank">灵神的题解</a></blockquote>好一道数据结构题目。长话短说吧，其实这道题就是链表的头插法。只不过并没有创建新链表，而是把这个节点本身给十分巧妙的原地使用了头插法，从而实现O(1)额外空间的链表反转。直接上代码，上完代码之后再讲：<pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
ll MOD = 1000000007;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
 ListNode* reverseList(ListNode* head) {
 ListNode *cur = head,*pre=nullptr;
 while (cur) {
 auto nxt = cur-&gt;next; //是为了存储丢失的cur后继节点信息
 cur-&gt;next = pre;
 pre=cur;
 cur=nxt;
 }
 return pre;
 }
};</code></pre>头插法，顾名思义，我们需要把新元素给插在头节点的前面，并且新元素本身成为头节点。因此，如果将一个序列按照从左到右的顺序，使用头插法插入链表当中，自然而然就实现了反转的效果。在这道题的题解代码中，我们使用了pre作为前驱节点(也算是反转后链表的后继节点)，cur作为当前节点，我们的目标就是，既保证cur能够沿着当前链表的方向往后走，又能让它的前驱节点成为它的后继。这时候我们就需要一个中间变量来暂时存储cur的后继，以确保cur在指向pre之后，还能继续往后走。在往后走之前，由于当前节点到了下一个节点就变成了前驱节点，因此需要用pre存储一下当前节点，然后cur再往后走。大体思路就是这样，虽说是头插法，但是原地头插反转链表的算法我还是第一次见，挺新奇的。这题还有个做法是递归法，是灵神题解里面的第一种方法，我这边就不讲了，感兴趣的同学自己去探索吧。<h1>22-234 回文链表</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/palindrome-linked-list/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/palindrome-linked-list/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：简单解题日期：2026.1.29标签：栈 递归 链表 双指针推荐题解：<a class="no-external-link" href="https://leetcode.cn/problems/palindrome-linked-list/solutions/2952645/o1-kong-jian-zuo-fa-xun-zhao-zhong-jian-rv0f3/?envType=study-plan-v2&envId=top-100-liked" target="_blank">灵神的题解</a></blockquote>这道题还是比较有意思的，从灵神的题解看来，我们需要做两道前置题目：反转链表和链表的中点。前者就是上一道题，后者我还确确实实没做过。当然，按照我一贯欧美的作风，我肯定是不会去做那道题的。于是我直接看了一眼代码，好像也不是很难。那就直接讲吧。首先讲讲前置知识：如何找到链表的中点？总体思路很简单：使用快慢指针。快指针一次往后两格，慢指针一次往后一格，当块指针无法继续往后两格时(要么指向最后一个节点，要么指向null)，慢指针指向的位置就是链表的中点(如果是奇数长度，那就是正中央；如果是偶数长度，那就是中线偏右的那个节点)。这道题为啥需要用到上面两道前置题目呢？因为我们需要先找到链表的中点，然后再将链表的后半段原地反转，反转完之后，就相当于一个链表先被劈成两半，然后被反转之后，后一半的尾巴和前一半的尾巴可能重叠(链表长度为奇数)，也可能各自分离(链表长度为偶数)。然后呢，我们就可以从这两个新链表的头部开始，一步一步往后同时遍历，一边遍历一边比较，若有不相等就直接返回<code>false</code>，两条链表都遍历完了就返回<code>true</code>。思路讲完了，上代码：<pre><code class="lang-cpp">class Solution {
public:
 bool isPalindrome(ListNode* head) {
 //1.先找链表中点
 ListNode *slow=head,*fast=head;
 while (fast &amp;&amp; fast-&gt;next) {
 slow=slow-&gt;next;
 fast=fast-&gt;next-&gt;next;
 }
 //2.反转后半段
 ListNode *pre=nullptr,*cur=slow;
 while (cur) {
 ListNode *nxt = cur-&gt;next;
 cur-&gt;next = pre;
 pre=cur;
 cur=nxt;
 }
 //3.开始比较
 ListNode *p1=head,*p2=pre; //这里需要注意，后半部分反转后的链表的头结点是pre，不是cur，cur已经指向null了
 while (p1 &amp;&amp; p2) {
 if (p1-&gt;val!=p2-&gt;val) return false;
 p1=p1-&gt;next;
 p2=p2-&gt;next;
 }
 return true;
 }
};</code></pre>其实完全可以像灵神题解里面一样，把上面两道前置知识的题目封装在函数里面，然后直接调用获取后半反转后链表的头结点即可。<h1>23-141 环形链表</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/linked-list-cycle/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/linked-list-cycle/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：简单解题日期：2026.1.29标签：哈希表 链表 双指针推荐题解：<a class="no-external-link" href="https://leetcode.cn/problems/linked-list-cycle/solutions/1999269/mei-xiang-ming-bai-yi-ge-shi-pin-jiang-t-c4sw/?envType=study-plan-v2&envId=top-100-liked" target="_blank">灵神的题解</a></blockquote>这道题的做法也是挺妙的：利用了操场上跑的慢的人一定会被跑的快的人"套圈"的原理。那么我们就能很自然的联想到快慢指针用快慢指针来做这道题。当然，看到题目第一眼，我是没想出来要这样做的。瞟了一眼题解才突然恍然大悟。"套圈"的概念，具象化到这道题，其实也简单：如果快指针到终点了也没和慢指针相等过，说明无环；由于只要不到终点，就会一直走，所以如果快指针和慢指针在某一时刻相等了，就说明是环，直接返回true。上代码：<pre><code class="lang-cpp">class Solution {
public:
 bool hasCycle(ListNode *head) {
 ListNode *slow=head,*fast=head;
 while (fast &amp;&amp; fast-&gt;next) {
 slow=slow-&gt;next;
 fast=fast-&gt;next-&gt;next;
 if (fast==slow) return true;
 }
 return false;
 }
};</code></pre>就讲到这里。<h1>24-142 环形链表 II</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/linked-list-cycle-ii/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/linked-list-cycle-ii/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：中等解题日期：2026.1.30标签：哈希表 链表 双指针推荐题解：<a class="no-external-link" href="https://leetcode.cn/problems/linked-list-cycle-ii/solutions/1999271/mei-xiang-ming-bai-yi-ge-shi-pin-jiang-t-nvsq/?envType=study-plan-v2&envId=top-100-liked" target="_blank">灵神的题解</a></blockquote>从题号也可以看出来，上面这道题就是这道题的前置题目。也是，毕竟我们得先判断题目给的链表是不是环，才能进行下一步。那么在套用上面这道题的方法，判断完这个链表是不是环之后，我们下面该怎么找链表入口呢？并且只用O(1)的额外空间。一开始我也想不出来，看了题解还是理解了大半天，也终于是理解了。其实还是快慢指针。<img src="https://pic.leetcode.cn/1741414978-wPTZwJ-lc142-3-c.png" alt="图解" title="图解" style="">从灵神的题解偷一张图过来。题解文字描述的上半段没啥问题，很好理解，我相信大多数同学(包括我自己)的理解问题都主要出现在下半段文字吧？那我换个方式讲一下。首先，由于快指针的速度是慢指针的2倍，当他们相遇时，快指针走过的总距离一定是慢指针的2倍，因此前者2b后者b，这很好理解。然后，由于是套圈，于是快指针比慢指针多走的那部分距离(即<code>2b-b=b</code>)一定一定一定是这个环长度的整数倍。因此，这里我们可以获得一个很重要的结论：因为b是环长度的整数倍，所以，从这个环上某一点开始，往后走b步，一定会回到原地。再回到上面这张图，是不是回想起来了？b同时也是链表起点到相遇点的距离！然后呢，由于我们要求的环的入口距离起点的距离是a，并且我们还得直接返回这个节点，于是我们就要想办法让这两个指针一起指向这个节点。这如何做到呢？我们可以把快慢指针其一(这里我选择慢指针)丢回起点，然后把快指针留在相遇点，然后让它们继续往后以相同的速度走。这时候会发生什么呢？先看慢指针这边，相较于起点走了a步，会到入环的节点；再看快指针这边，它站在相遇点，如果它也再走a步，再加上它之前走了b步，那么它相较于起点走过的总路程就是<code>b+a</code>步。还记得b是环长度的整数倍吗？这就说明，相较于起点走了<code>b+a</code>步就和走了a步的效果是一模一样的。换句话说，走a步之后，快指针也会到达入环节点！这时候，我们直接挑选快慢指针其一返回即可。这道题的逻辑确实挺绕的。<pre><code class="lang-cpp">class Solution {
public:
 ListNode *detectCycle(ListNode *head) {
 //1.先判是否为环
 ListNode *slow=head,*fast=head;
 bool flag=false;
 while (fast &amp;&amp; fast-&gt;next) {
 slow=slow-&gt;next;
 fast=fast-&gt;next-&gt;next;
 if (slow==fast) {
 flag=true;
 break;
 }
 }
 if (!flag) return nullptr;
 //2.把slow放回起点，各自一步一步走，再次汇聚即为入环点
 slow=head;
 while (slow!=fast) {
 slow=slow-&gt;next;
 fast=fast-&gt;next;
 }
 return slow;
 }
};</code></pre>就讲到这里。<h1>25-21 合并两个有序链表</h1><blockquote>题目链接：<a class="no-external-link" href="https://leetcode.cn/problems/merge-two-sorted-lists/description/?envType=study-plan-v2&envId=top-100-liked" target="_blank">https://leetcode.cn/problems/merge-two-sorted-lists/description/?envType=study-plan-v2&envId=top-100-liked</a>难度：简单解题日期：2026.1.30标签：哈希表 链表 双指针推荐题解：无</blockquote>这道题也是一道经典的数据结构题目，总体思路很简单，和合并两个升序数组一样：维护两个指针，都指向两条链表的头部，每次都选小的那个插在新链表的头部。对，基本思路就这么多，然后我去实现了，欧美打法，自信满满的写了一坨史山代码：<pre><code class="lang-cpp">class Solution {
public:
 ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
 ListNode *p1=list1,*p2=list2,*list3 = nullptr;
 //1.选择头结点
 if (p1 &amp;&amp; p2) {
 if (p1-&gt;val&lt;p2-&gt;val) {
 list3=p1;
 p1=p1-&gt;next;
 }else {
 list3=p2;
 p2=p2-&gt;next;
 }
 }else {
 if (p1) {
 list3=p1;
 p1=p1-&gt;next;
 }else if (p2){
 list3=p2;
 p2=p2-&gt;next;
 }else {
 return nullptr;
 }
 }
 ListNode *p3=list3;
 //2.开始两头工作
 while (p1 || p2) {
 if (p1 &amp;&amp; p2) {
 if (p1-&gt;val&lt;p2-&gt;val) {
 p3-&gt;next=p1;
 p1=p1-&gt;next;
 }else {
 p3-&gt;next=p2;
 p2=p2-&gt;next;
 }
 }else if (p1) {
 p3-&gt;next=p1;
 p1=p1-&gt;next;
 }else if (p2) {
 p3-&gt;next=p2;
 p2=p2-&gt;next;
 }
 p3=p3-&gt;next;
 }
 //3.收尾与返回
 p3-&gt;next=nullptr;
 return list3;
 }
};</code></pre>基本思路就是写了一堆复杂逻辑，先确定头结点，然后再用差不多的逻辑把小的优先接在链表头，最后再收尾返回头结点。但是其实根本不需要这么麻烦。我们引入哨兵的概念：新定义一个空白节点作为头结点，它的next指向null，这样就可以跳过开头的选头结点的过程了，直接进循环开插。循环里面的逻辑也可以大大简化：我们只处理两个链表都没遍历完的情况，正常比较取小插入即可。当其中一个链表跑完之后，再把剩下没跑完的链表直接接在新链表的尾部，不需要再重新遍历了，要学会利用链表的特性。基本思路就是这样，上代码：<pre><code class="lang-cpp">class Solution {
public:
 ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
 ListNode dummy(0);
 ListNode *tail = &amp;dummy;
 while (list1 &amp;&amp; list2) {
 if (list1-&gt;val&lt;list2-&gt;val) {
 tail-&gt;next=list1;
 list1=list1-&gt;next;
 }else {
 tail-&gt;next=list2;
 list2=list2-&gt;next;
 }
 tail=tail-&gt;next;
 }
 if (list1) {
 tail-&gt;next=list1;
 }else {
 tail-&gt;next=list2;
 }
 return dummy.next;
 }
};</code></pre>就讲到这里。

前言

1-1 两数之和

2-49 字母异位词分组

3-283 移动零

4-128 最长连续序列

1. 哈希碰撞（主要原因）

2. 重复元素遍历（次要原因）

5-11 盛最多水的容器

6-15 三数之和

7-3 无重复字符的最长子串

8-438 找到字符串中所有字母异位词

9-560 和为 K 的子数组

10-239 滑动窗口最大值

11-76 最小覆盖子串

12-56 合并区间

13-189 轮转数组

14-238 除了自身以外数组的乘积

15-41 缺失的第一个正数

16-73 矩阵置零

17-54 螺旋矩阵

18-48 旋转图像

19-240 搜索二维矩阵 II

20-160 相交链表

21-206 反转链表

22-234 回文链表

23-141 环形链表

24-142 环形链表 II

25-21 合并两个有序链表

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

LeetCode Hot100解题笔记 260130更新

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款