前言

有点惊讶吧？这个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])低。此时，我们有两种选择：

  1. 移动左边的指针：l++。由于不管移动左边还是右边，长度都是d-1，所以面积的大小就由两边最短的木板决定了。并且呢，无论左边的指针怎么动，左边的木板高度变成咋样，根据木桶效应，决定面积的那个木板的高度绝对不会超过右边的木板。已知左边的高度就是比右边低，所以挪动l，木板的高度(h[l])可能会变大，也可能会变小。如果h[l]变小，已知d->d-1，所以面积一定会变小；如果h[l]变大，虽然d变小了，但是只要h[l]变的足够大，大到抵消d的损失，面积还是有可能反而变大的。

    总结：移动左边的指针，面积可能变大也可能变小，相当于搏一搏，找个机会。

  2. 移动右边的指针：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.盛最多水的容器。我们先把这个数组升序排序。这是为了：

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

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

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

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

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

  1. 如果sum>0，那说明选的数大了，我们需要选更小的。将大的数换掉，r--。
  2. 如果sum<0，那说明选的数小了，我们需要选更大的。将小的数换掉，l++。
  3. 如果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换成其他数据结构会发生啥？

  1. 换成 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。
  1. 换成原生数组 int[26]

结论：性能最强，但代码灵活性降低。

  • 内存： 原生数组分配在栈上，省去了 vector 在堆上动态申请空间的开销（虽然本题只申请一次，影响较小）。

  • 痛点：比较操作。 在 C++ 中，原生数组不能直接用 == 比较（arr1 == arr2 比较的是首地址指针）。

    • 你需要手动写一个循环比较 26 个位置。
    • 或者使用 memcmp(cnt, key, sizeof(cnt))。
  1. 最优选：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)$。

  1. 核心思想：删除“冗余”元素

在一个窗口内，如果 $i < j$ 且 $nums[i] \leq nums[j]$，那么只要 $nums[j]$ 还在窗口里，$nums[i]$ 就永远不可能成为最大值。

  • $nums[j]$ 比 $nums[i]$ 更大。

  • $nums[j]$ 比 $nums[i]$ 在窗口里停留的时间更长（更晚过期）。

    因此，$nums[i]$ 就是“冗余”的，可以直接丢弃。

  1. 算法流程

使用 std::deque（双端队列）维护一个下标序列，并保持队列对应的元素值严格单调递减：

  1. 入队：当新元素 nums[i] 进入时，从队尾弹出所有小于等于它的元素（因为它们冗余了）。
  2. 出队（维护窗口）：检查队头下标是否已超出窗口范围（即 dq.front() == i - k），若是则弹出。
  3. 取最值：此时队头下标对应的元素即为当前窗口的最大值。
  4. 代码实现
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;
}
  1. 复杂度对比
算法时间复杂度空间复杂度备注
优先队列（延迟删除）$O(n \log n)$$O(n)$简单直观，依赖堆的自动排序
单调队列$O(n)$$O(k)$极致优化，每个元素仅入队/出队一次

好的，那就讲到这里。

最后修改：2026 年 01 月 06 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏