力扣刷题笔记 #01 数组

本文包含「数组」类型题中的：哈希表、前缀和/差分、离散化、排序/选择、双指针等技巧。持续更新中。

题目描述：

方法1：

方法2：

方法3：

坑点：

哈希表

1. 两数之和 (E+)

题目描述：给定一个数组，在数组中找出两个整数，使两数之和为指定值，并返回两数下标。

方法1：暴力枚举，两层循环顺序遍历，复杂度 \(O(n^2)\)。

方法2：哈希表，注意到内层循环本质是「快速查找目标值的索引」，用哈希表可 \(O(1)\) 查找，总复杂度 \(O(n)\)。

坑点：当数组中有两个 key 相同时，如果先建哈希表，则会发生覆盖，然而由于每种输入只会对应一个答案，因此此时这两个 key 就必定是结果。解决方法是边建表边遍历，每次查找的都是遍历过的值。

128. 最长连续序列 (M)

题目描述：给定一个无序数组 nums，找出其中可以组成的最长连续序列（不要求序列元素在原数组中连续）的长度。

方法1：排序，先进行快速排序，再用一个指针扫描数组即可。时间复杂度 \(O(n\log n)\)。

方法2：哈希集合，先将原数组存入哈希集合，既能去重又能快速定位元素。遍历哈希集合，对每个 \(x\) 寻找 \(x+1\)，直到找到最长序列。为了防止同一个序列重复判断，每次先检查 \(x-1\) 是否存在，如果存在则跳过。时间复杂度 \(O(n)\)。

方法3：哈希表 + 并查集，维护每个集合的大小，对于元素 \(x\) 合并 \(x +1\)，并更新最大集合，时间复杂度 \(O(n)\)。

169. 多数元素 (E)

题目描述：给定一个大小为 \(n\) 的数组，返回其中的多数元素，即数组中出现次数大于 $n/2 $ 的元素。

方法1：哈希表，直接统计每个元素出现的次数，同时维护最大值，时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。

方法2：排序，由于众数次数超过了一半，下标为 $n/2 $ 的元素一定是众数。时间复杂度 \(O(n\log n)\)。

方法3：随机选取一个数，遍历检查，如果不是再重新选。期望次数为 \(2\)，时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

方法4：半数投票法，顺序扫描，假设有一个擂台，\(cnt\) 为擂台上的人数。当擂台没人时直接上台；如果有人且是同伙则上台，\(cnt+1\)；如果不是同伙则打败一个，\(cnt-1\)。由于众数超过了一半，最终一定能打败非众数，最后剩余的就是多数元素。时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

1124. 表现良好的最长时间段 (M)

题目描述：给定一个仅包含 \(\pm 1\) 的数组，求解区间分数和大于 \(0\) 的最长区间长度。

方法1：前缀和，预处理得到前缀和之后，暴力枚举区间左右端点，时间复杂度 \(O(n^2)\)，超时。

方法2：前缀和连续性 + 哈希表，只枚举区间右端点，此时我们希望找到最小的 \(l<r\) 满足 \(pre[l]<pre[r]\)，使用哈希表记录每一个前缀和第一次出现的位置，可以优化寻找过程，时间复杂度 \(O(n)\)。

由于 \(pre[0]=0\)，所以要根据 \(pre[r]\) 是否大于零来讨论：

• 如果 \(pre[r]>0\)，则左端点最小就是 \(l=0\)，此时的最长长度为 \(r+1\)。
• 如果 \(pre[r] \leq 0\)，则要在其左边找到满足 \(pre[l] = pre[r]-1\) 的位置。为什么是 \(-1\) 而不是更小的数？因为 \(pre[0]=0\)，而前缀数组每次只能 \(\pm 1\)，所以 \(pre[r]-1\) 一定比 \(pre[r]-2\) 更靠左！

方法3：贪心 + 单调队列 + 栈，能成为最长子数组的左端点的元素必然构成一个递减序列，因为如果来了一个大于等于栈顶的元素，则栈顶元素一定能比新元素构成更长的区间。这里单调队列用栈实现。因此先正向遍历获得单调递减栈，再反向遍历枚举右端点，每遇到比栈顶更大的元素就更新答案并弹出元素。时间复杂度 \(O(n)\)。

前缀和/差分

前缀和需要 \(O(n)\) 构建，此后可以多次 \(O(1)\) 查询区间和，但不支持单点或区间的快速修改，每次修改需要 \(O(n)\)。

• 这类题目通常要求「访问、找到、计数」一个连续子数组，并且统计量具有前缀性质。
• 此外，前缀和还有其他变式：前缀和的模、前缀积、前缀出现次数等。

差分数组也需要 \(O(n)\) 构建，此后可以多次 \(O(1)\) 加减更新区间值，但最后需要进行一次前缀和才能恢复原始数组。

• 这类题目通常要求「改变、划分」多个连续子数组，并且每次对多个连续元素执行操作。
• 如果要求除了加减外的其他操作，则应该考虑单次操作 \(O(\log n)\) 的线段树维护。

有时候需要二维数组的前缀和、差分，用于求二维数组中给定矩阵区间和，或者给矩阵区间的每个值都加上常数，下面给出常用代码。

// 原始数组 nums 转前缀和数组 pre，pre[i][j] 表示 (i,j) 以外的左上角的矩阵之和
vector<vector<int>> pre(n + 1, vector<int>(m + 1, 0));
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
        pre[i][j] = nums[i-1][j-1] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];
// 查询左上角为 (x1,y1)，右下角为 (x2,y2) 的矩阵和
res = pre[x2+1][y2+1] - pre[x1][y2+1] - pre[x2+1][y1] + pre[x1][y1];

// 原始数组 nums 转差分数组 diff, 没有实际意义
vector<vector<int>> diff(n + 1, vector<int>(m + 1, 0));
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
        diff[i][j] = nums[i][j] - nums[i-1][j] - nums[i][j-1] + nums[i-1][j-1];
// 对左上角为 (x1,y1)，右下角为 (x2,y2) 的矩阵加上常数 c
diff[x1][y1] += c;
diff[x1][y2+1] -= c;
diff[x2+1][y1] -= c;
diff[x2+1][y2+1] += c;

// diff 恢复为原始数组，此时 diff 可以迭代更新，再去除首行和首列
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
        diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1];
// diff 恢复为原始数组，采用另一种方式，得到 n*n 的数组
vector<vector<int>> ans(n, vector<int>(n));
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) ans[i][j] = diff[i][j];
for (int i = 0; i < n; i++) for (int j = 1; j < n; j++) ans[i][j] += ans[i][j - 1];
for (int i = 1; i < n; i++) for (int j = 0; j < n; j++) ans[i][j] += ans[i - 1][j];

2406. 将区间分为最少组数 (M)

题目描述：给定一些整数区间，将其划分为若干区间组，使得每组区间都不相交（区间端点也不能重叠）。返回最少需要划分的组数。

方法1：贪心 + multiset，先按区间起始值排序，在集合中记录已有区间组的末尾值，每次新区间加入时在集合中找到可以插入的最大值，并更新该值为新区间的末尾值。时间复杂度为 \(O(n\log n)\)。

方法2：优先队列，由于排过序，每次新区间加入时可以直接插入任意一个可插入的区间，因为无论选哪个，下一个新区间面临的选择还是那些。因此选择已有的最小末尾值（最容易插入的），维护最小堆，时间复杂度为 \(O(n\log n)\)。

方法3：差分 + 前缀和，如果有重叠数字则必须分到不同区间组，最高的重叠次数就是答案。从前往后枚举，用差分数组记录对应每个区间的计数，最后通过前缀和还原数组取最值即可。时间复杂度为 \(O(N)\)，\(N\) 为整数范围。

拓展：本题的另一个问法 253. 会议室 II，给定 \(n\) 个会议的起止时间，计算至少分配多少间会议室才能避免会议冲突。

238. 除自身以外数组的乘积 (M)

题目描述：给定一个整数数组 nums，返回另一个答案数组，要求每个位置为 nums 中除 nums[i] 外其余各元素的乘积。保证不会溢出，禁止使用除法。

方法1：尝试使用除法，直接计算所有元素的乘积再除以对应位置的值，但在数组中有零元素时会出错，需要特判。

方法2：前后缀乘积，预处理出两个前后缀数组，每个位置直接算出答案。时空复杂度均为 \(O(n)\)。

方法3：前后缀 + 在线计算，正向遍历时用 \(L\) 维护下标 \([0,i]\) 的前缀乘积并放入答案数组，反向遍历时用 \(R\) 维护 \([n-1-i,n-1]\) 的后缀乘积更新答案数组。空间复杂度优化到 \(O(1)\)，也可以只用一次遍历完成。

---

以下为「前缀和 + 哈希表计数」类型题，这类题目通常要求统计一类连续子数组的个数，需要枚举一侧端点。

560. 和为 K 的子数组 (M)

题目描述：给定整数数组 nums 和整数 k，统计并返回该数组中和为 k 的连续子数组的个数 。

方法1：暴力，本题不能用滑动窗口的原因是数组有正有负，不能提前移动左指针，因此使用两层循环。外层枚举左端点，内层枚举右端点，区间和累加计算，复杂度 \(O(n^2)\)，超时。

方法2：前缀和 + 哈希表，枚举左端点 \(i\)，则 \(i\) 到右端点之和为 \(k\)，左侧之和为 \(pre[i]\)，两边相加就是右端点的前缀和，因此需要用哈希表计数前缀和为 \(k+pre[i]\) 的个数，时空复杂度均为 \(O(n)\)。

注意，由于数组有正有负，前缀和为 \(k+pre[i]\) 的数组可能在 \(i\) 的左侧，记得要扣除这部分。实际操作中只需要在枚举完一个左端点 \(i\) ，将其前缀和 \(pre[i+1]\) 的次数减去 \(1\) 即可，确保枚举过的左侧点不再参与计算。

方法3：空间优化，先枚举右端点，在枚举 \(pre[i] - k\) 的前缀和次数，则枚举的过程可以和前缀和一起处理，且不需要再扣除（因为后面的还没遍历到）。前缀和的空间也可以用一个变量存放，空间优化。

523. 连续的子数组和 (M)

题目描述：给定整数数组 nums 和整数 k，判断是否含有总和为 k 的倍数、长度至少为 \(2\) 的连续子数组。

方法1：暴力，两层循环枚举左端点和右端点，区间和累加，时间复杂度 \(O(n^2)\)，超时。

方法2：前缀和 + 哈希表，由同余定理，哈希表只要存储 \(sum\%k\) 的结果。而本题只要判断不需要计数，因此存储每个值第一次出现的下标。同时枚举右端点 \(i\)，只需看哈希表中 \(pre[i]\) 的下标距离是否超过 \(2\)，复杂度 \(O(n)\)。

方法3：前缀和 + 哈希集合，由于本题距离下限固定为 \(2\)，在枚举右端点时，依次进行「哈希查询、哈希插入、前缀和更新」，就能避免找到长度 \(<2\) 的连续子数组。更容易实现，复杂度 \(O(n)\)。

坑点：方法 2 中要初始化 \(hash[0]=-1\)，即没有元素时的前缀和为 \(0\)。

1248. 统计「优美子数组」(M)

题目描述：给定整数数组 nums 和整数 k，如果某个连续子数组中恰好有 k 个奇数数字，则称为「优美子数组」。

方法1：暴力，两层循环枚举左端点和右端点，区间和累计，时间复杂度 \(O(n^2)\)，超时。

方法2：乘法原理，建立一个纯奇数的 \(odd\) 数组，存储奇数 \(i\) 出现的位置，枚举每个奇数 \(i\)，其对答案的贡献是其左右边界的范围乘积，时间复杂度 \(O(n)\)。

方法3：前缀次数 + 哈希表，哈希表记录前缀次数为 \(k\) 的个数，当统计到 \(i\) 时，在哈希表中查找 \(pre[i]-k\) 的个数即可，复杂度 \(O(n)\)。

坑点：方法 3 中要初始化 \(hash[0]=1\)，即一开始有 \(0\) 个奇数数字。

437. 路径总和 III (H)

题目描述：给定一个二叉树的根节点和一个目标整数，求二叉树中节点之和为目标值的路径数目。这里的路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的。

方法1：暴力 DFS，DFS 枚举每个节点作为路径头时的情况，再向下 DFS 到叶节点，总共有两层 DFS，时间复杂度 \(O(n^2)\)，空间复杂度 \(O(n)\)。

方法2：前缀和 + 哈希表，DFS 遍历时记录根节点到当前节点的和 \(cur\)，并用哈希表计数，每次查询 \(cur-target\) 的个数。为了防止不同分支影响计数，DFS 回溯时需要删去哈希表中的记录。注意初始化 hash[0]=1，如果从根节点到当前节点恰好等于目标，差值就是 \(0\)。时间复杂度 \(O(n)\)。

坑点：本题的方法 1 中，记忆化数组并不能优化时间复杂度，因为需要存储的关键字有两个，必须用 pair，且只能用 map 映射，常数较大。而且两个关键字组成的目标域太过稀疏，重复访问的概率很小。

2488. 统计中位数为 K 的子数组 (H)

题目描述：给定一个 \([1,n]\) 的排列数组，统计其中位数为整数 \(k\) 的连续子数组数目，长度为偶数时中位数算靠前者。

方法1：暴力，找出中位数，从中间开始向两边遍历，同时累计大于、小于 \(k\) 的个数，复杂度 \(O(n^2)\)，超时。

方法2：前缀次数 + 哈希表，\(k\) 为中位数意味着「左侧小于 + 右侧小于 (+1) = 左侧大于 + 右侧大于」，因此需要计数两侧大于、小于 \(k\) 的数的个数。利用前缀次数处理，再将两侧「大于 - 小于」的值出现次数存入两个哈希表，遍历哈希表，用乘法原理算出结果，时间复杂度 \(O(n)\)。

方法3：正负性转换 + 哈希表，大于 \(k\) 的数可视为 \(+1\)，小于 \(k\) 的数视为 \(-1\)。从 \(k\) 所在位置开始，先向左扫描同时累计 \(lsum\)，并用哈希表记录 \(lsum\) 的出现次数；再向右扫描累计 \(rsum\)，看哈希表中有多少个 \(lsum\) 可以配对。时间复杂度 \(O(n)\)。

离散化

解决数据范围大但样本点少的情况，将大范围的样本（连续取值）映射到小范围（离散取值）。

sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
int m = nums.size(); // 去重后的长度

850. 矩形面积 II (H)

题目描述：给定一组 X-Y 轴对齐的矩形（左上角和右下角坐标），计算平面中所有矩形覆盖的总面积，重叠部分只算一次。

方法1：离散化 + 扫描线，对所有矩形的左右边界排序，横坐标离散化成 \(2n\) 个点，纵坐标去重成 \(\leqslant2 n-1\) 个线段。遍历横坐标，每次对一批横坐标相同的左右边界遍历纵坐标线段，复杂度 \(O(n^2)\)。

扫描线算法：用一条竖直的直线从平面的最左端扫到最右端，扫描过程中直线会被给定的矩形覆盖，对覆盖的线段进行积分。每次扫到矩形的左边界时，覆盖的长度可能会增加；扫到矩形的右边界时，覆盖的长度可能会减少。

离散化，分别对横纵坐标处理：

• 由于矩形的横坐标是连续值（\(1e9\)），而矩形的个数 \(n \leqslant 200\)，可以将其转化为 \(2n\) 个离散的横坐标。

• 纵坐标将扫描线划分作 \(2n-1\) 个线段（共有 \(2n\) 个离散的坐标，去掉两端的射线），因此可以用两个长度为 \(2n-1\) 的数组维护。 \(seg[i]\) 表示第 \(i\) 个线段被覆盖的次数，\(length[i]\) 表示第 \(i\) 个线段的长度。遇到一个左边界时，我们就将左边界覆盖到的线段对应的 \(seg[i]\) 全部加 \(1\)；遇到一个右边界时，我们就将右边界覆盖到的线段对应的 \(seg[i]\) 全部减 \(1\)。处理完一批后，\(seg[i]\) 如果大于 \(0\)，说明它被覆盖，将 \(length[i]\) 累加，即可得到「覆盖的线段长度」。

方法2：离散化 + 扫描线 + 线段树，维护 \(seg\) 数组的覆盖次数，以及离散化后的 \(length\)。需要区间加、减操作，对于所有非 \(0\) 的位置，按照 \(length\) 求和。复杂度 \(O(n \log n)\)。

双指针

常见的有分段双指针、并行双指针、快慢双指针、对撞双指针、滑动窗口双指针：

• 分段双指针：两个指针将序列分为三段，最右边是未访问的，左边和中间的序列往往具有特定属性。
• 并行双指针：两个指针分别遍历两个序列，遍历到的值进行某种操作，并使其中一个指针前进。
• 快慢双指针：常用于链表中，解决需要「计数」的问题。
• 对撞双指针：两个指针从两端开始向中间靠拢，通常使用 while(left < right)。
• 滑动窗口双指针：关注窗口内的值，题目中通常会有「最长连续子 XX」，关键在于「连续」。

283. 移动零 (E)

题目描述：将数组 nums 中的所有 0 移动到数组的末尾，同时保持非零元素的相对顺序，要求原地操作。

方法1：冒泡，不改变相对顺序，将所有 0 冒泡移动末尾，复杂度 \(O(n^2)\)。

方法2：分段双指针，左指针左边均为处理过的非零数，右指针左边直到左指针本身均为零，右指针右边是未处理的序列。右指针向右移动，每次遇到非零数，就和左指针指向的零交换，同时左指针右移。复杂度 \(O(n)\)，交换的次数是非零数的个数。

方法3：直接遍历，遍历时计数 0 的个数，每次遇到非零数直接往前填充，最后再填充所有零。复杂度 \(O(n)\)，覆盖次数是非零数的个数 + 零的个数，也就是数组的长度。

11. 盛最多水的容器 (M)

题目描述：给定一个长度为 n 的数组表示 n 条垂线的高，找出其中两条线，使它们构成的容器能装最多的水。

方法1：暴力，两层循环，先选中左边界，再遍历右边界，时间复杂度 \(O(n^2)\)。

方法2：贪心 + 对撞双指针，双指针从两端开始遍历，选定两个边界中的短板，向中间收窄一格。时间复杂度 \(O(n)\)。

如果长板向内收窄则不可能得到更优解，因为「短板」只可能更短，而横轴也变短了。

15. 三数之和 (M)

题目描述：给定一个整数数组，返回其中所有不重复的三元组，使其和为零。三元组中可以有相同数。

方法1：排序 + 暴力，将数组从小到大排序后，三层循环遍历，且每层循环都大于上一层循环枚举的元素，可以保证三元组 a<=b<=c，不会有其他顺序。同时对每一层循环跳过相同的数，否则也会重复。时间复杂度 \(O(n^3)\)。

方法2：排序 + 二分查找，方法 1 的第三层遍历中，目标数值是确定的，因此可以直接二分查找 binary_search(num+b_idx, num+n, c)，时间复杂度 \(O(n^2 \log n)\)。

方法3：排序 + 对撞双指针，方法 1 的第三层遍历中，如果 b 匹配到了一个元素 c，则下一次 b<=b' 时一定有 c'<=c，因此无需完整遍历，只需用双指针从两端向中靠拢。时间复杂度 \(O(n^2)\)。

拓展：这题的解法也可以照搬到 四数之和，只是多了一层循环。

16. 最接近的三数之和 (M)

题目描述：给定一个整数数组和一个目标值 target ，从数组中选出选出三个整数，使它们的和与 target 最接近。

方法1：暴力，三层循环遍历，时间复杂度 \(O(n^3)\)，可以通过排序进行一定的剪枝。

方法2：排序 + 对撞双指针，外层循环不变，内层循环改用对撞双指针，同时维护一个变量 \(diff\) 表示和目标差值的绝对值。内层循环时会被 \(sum \pm diff\) 划分为五种情况，时间复杂度 \(O(n^2)\)。

五种情况分别为：和小于 \(sum-diff\) 时左指针移动，和大于 \(sum + diff\) 时右指针移动；其他情况需要更新 \(diff\) 值，并且根据和与 \(sum\) 的关系判断三种情况。

75. 颜色分类 (M)

题目描述：给定一个由数字 0 1 2 组成的数组，代表三种颜色（荷兰国旗问题），按照 0<1<2 的顺序原地排序。

方法1：单指针两次遍历，用指针维护「已归位」元素下标，第一次遍历找出数字 \(0\) 放到指针处，并将指针后移；第二次遍历找出数字 \(1\) 放到指针处。两次遍历完 \(2\) 都出现在尾部。时间复杂度 \(O(n)\)。

方法2：分段双指针，用指针 \(p_0\) 维护下一个 \(0\) 的位置，指针 \(p_1\) 维护下一个 \(1\) 的位置。每次遇到 \(1\) 则将其交换到 \(p_1\)，并将 \(p_1\) 增一；每次遇到 \(0\) 则将其交换到 \(p_0\)，由于 \(p_0\) 处可能放着 \(1\)，所以还要将其放到 \(p_1\) 位置，最后将两个指针增一。

方法3：对撞双指针，左指针 \(p_0\) 维护下一个 \(0\) 的位置，右指针 \(p_2\) 维护下一个 \(2\) 的位置。从左往右遍历，遇到 \(0\) 直接换，遇到 \(2\) 交换后，当前位置换来的数可能还是 \(0\) 或 \(2\)，需要一直重复交换直到当前位置为 \(1\)。

此时遍历用的迭代变量可以理解为 \(p_1\)，因为本题的目的就是划分三个区间，用三个指针是最符合直觉的。

42. 接雨水 (H)

题目描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

方法1：暴力，对于每个坐标，其能接的水量取决于左右两边最高的柱子中较矮者，两层循环遍历，复杂度 \(O(n^2)\)。

方法2：DP 预处理最大值，两次扫描，记录每个柱子的左右两边最大值，再扫描累计，时空复杂度均为 \(O(n)\)。该方法可以简单优化：从左到右的预处理可以和第三次扫描合并，用一个变量存储左边最大值，节省一个数组。

方法3：单调栈 + 模拟，每遍历到一个柱子，如果比栈顶元素更小则入栈，如果更大则说明前面的柱子可以形成水洼，则依次将所有较小数弹出，并计算和新柱子的距离差值，再把新柱子入栈。时空复杂度均为 \(O(n)\)。

方法4：贪心 + 对撞双指针，双指针从两端开始遍历，再用两个变量存储左右两边最大值，每次较小者向中间收窄一格，同时计算出当前柱子能接的水量。时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

较小者可以先计算的原因是：较小者可能会被更新为较大者，而较大者不可能会被更新为较小者。因此较小者此刻的解具有无后效性。

方法5：分治 + 面积法，最高柱子将全局分为两边，两边各有各自的次高柱子，次高柱子与最高柱子中间的区域显然取值就是「次高柱子 - 当前柱子」，同理以此类推到两端。时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

因此只需遍历一次，从左往右取左边最大值，从右往左取右边最大值，答案增加「左高 + 右高 - 当前柱子」。这里的减去的「当前柱子」只是为了减去所有柱子的面积（合并在一次遍历中完成）。

最后减去「最高柱子 \(\times\) 总长度」，因为两次扫描都会经过最高柱子，经过后再接着扫描的面积无意义，形成了一个大矩形的面积，需要扣除。

坑点：最左边、最右边两个柱子不可能接到水，要跳过，可以直接从 1 遍历到 n-2。

滑动窗口

双指针中较为困难的一类题：关注窗口内的值，题目中通常会有「连续子 XX」，关键在于「连续」。

• 要求「最长连续子 XX」的长度，此时应该尽量滑动右指针，在窗口不满足要求时滑动左指针。同时优化判断「窗口是否满足要求」的复杂度。此时维护的窗口类型：
  • 哈希集合：维护窗口内有哪些元素；
  • 哈希表：维护窗口内元素出现的次数、最后出现的位置；
  • 双哈希表：对子串乱序匹配问题，需要一个 need 存储目标次数、一个 window 维护窗口内出现的次数；
  • 单个变量：利用位运算进行存储、或者压位操作。
• 要求「连续子 XX」的个数，此时应该枚举右指针并固定（定界法），然后再枚举左指针，计数左指针的枚举次数。左指针不需要复位，防止退化为 \(O(n^2)\)。此时需要维护的变量：
  • 不该出现的元素的最后出现的位置，代表窗口左指针的最左取值；
  • 必须出现的元素的最后出现的位置，代表窗口左指针的最右取值。

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

题目描述：给定一个字符串 s，找出其中不含有重复字符的最长连续子串的长度。

方法1：双指针滑动窗口，右指针每前进一格，在窗口内进行 s.find，如果找到重复字符，则左指针快速前移，复杂度 \(O(n^2)\)。左右指针移动的方式也可以交换。

方法2：滑动窗口 + 哈希集合，左指针多次 erase() 直到 hash.count() == 0 代替 find，复杂度 \(O(n)\)。

方法3：滑动窗口 + 哈希表，比上一个方法多用一个数来存储字符在数组中的下标，左指针快速前移时不需要一直多次 count()，复杂度 \(O(n)\)。

438. 找到字符串中所有字母异位词 (M)

题目描述：给定两个字符串 s 和 p，找到 s 中所有 p 的字母异位词子串（相同字母重排列形成）。

方法1：定长滑动窗口，窗口长度限定为 p 的长度，枚举窗口的每个位置，用哈希表 + 计数来判断窗口内是否匹配所有字母，每次只考虑一进一出的两个字母，时间复杂度 \(O(n+m)\)。

方法2：滑动窗口 + 双哈希表，哈希表 need 记录目标字符次数，用双指针扫描母串并记录窗口内字符次数 window，左指针只在 \(window[s[l]]>need[s[l]]\) 时前移。用 \(cnt\) 维护已匹配字符数，当窗口长度恰好是 p 的长度时更新。时间复杂度 \(O(n+m)\)。

76. 最小覆盖子串 (H)

题目描述：给定字符串 s 和 t，找出 s 中涵盖 t 所有字符的最小子串，顺序可以打乱。

方法1：滑动窗口 + 双哈希表，哈希表 need 记录目标字符次数，用双指针扫描母串并记录窗口内字符次数 window，左指针只在 \(window[s[l]]>need[s[l]]\) 时前移。用 \(cnt\) 维护已匹配字符数，及时更新答案。复杂度 \(O(n+m)\)。

方法2：滑动窗口 + 单哈希表，哈希表 need 记录距离目标字符剩余次数，只有遇到 t 中存在的字符时才更新窗口，用 \(cnt\) 维护剩余字符数，及时更新答案。复杂度 \(O(n+m)\)。

2401. 最长优雅子数组 (M)

题目描述：正整数组成的数组 nums 中找出最长连续子数组，使其满足子数组中所有元素两两 & 结果等于 0。

方法：滑动窗口 + 位运算，窗口内所有元素取 | 使二进制 1 位合并，右侧元素只需和整体进行 & 就能判断是否加入窗口，如果不能加入，则左侧元素需要弹出，使用 ^ 运算去除二进制 1 位。

使用异或必定可以去除：因为窗口内任何二进制位上的 1 必定只出现一次（满足优雅子数组）。

---

795. 区间子数组个数 (M)

题目描述：给定一个整数数组 nums 和两个整数：left 及 right。找出连续、非空且最大值在 [left,right] 内的子数组，统计个数。

方法1：乘法原理，单调栈预处理每个数作为最大值时的两边边界，计算出个数贡献，时空复杂度均为 \(O(n)\)。

方法2：定界法，显然 >right 的数不能包含，记上一个出现的位置为 \(i_0\)；区间内的数至少包含一个，记上一个出现的位置为 \(i_1\)。枚举右端点，则当 \(i_0<i_1\) 时，两者的差就是个数。时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

2817. 统计定界子数组的数目 (H)

题目描述：给定一个整数数组 nums 和两个整数 minK 以及 maxK，若一个连续子数组中的最小值等于 minK，最大值等于 maxK，则称为定界子数组。返回定界子数组的数目。

方法1：分治 + 滑动窗口双指针，首先去掉范围之外的数，将原数组分为若干个子数组，再对每个子数组讨论。每个子数组采用双指针扫描，时间复杂度 \(O(n)\)。

对每个子数组，先枚举右端点，右指针滑动并计数 miCnt 和 mxCnt，当 miCnt > 0 && mxCnt > 0 时，说明右端点已经满足，此时左端点有多种取值。

枚举左端点，左指针滑动并减少 miCnt 和 mxCnt，当不满足条件时，左端点枚举过的距离就是该右端点对应的定界子数组个数。继续枚举下一个右端点。

对于下一个右端点，即使滑动窗口之间不满足 miCnt > 0 && mxCnt > 0，也可以增加左端点枚举过的距离，因为这段距离中任何一个左端点都可以和当前右端点构成定界子数组。

方法2：定界法，记录上一个范围之外的数的下标 \(i_0\)，代表了左端点的最左取值。枚举右端点，同时记录遍历过的距离右端点最近的 \(minK\) 和 \(maxK\) 的下标，二者中的靠左者就是左端点的最右取值。时间复杂度 \(O(n)\)。

坑点：不要试图将两边端点的取值范围找出来后相乘，因为这题每个点有两种角色，需要都满足时才能产生贡献。