目录
🌼和为K的子数组
O(n^2) 枚举
不用滑动窗口，有负值
超时，但过了 92 个样例，贴下思路👇
[0, i] 之间枚举 j，使得 [j, i] 区间和 == k
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n = nums.size(), ans = 0;
// 不要排序，会破坏原有顺序
for (int i = 0; i < n; ++i) {
int sum = 0;
for (int j = i; j >= 0; j--) { // 后往前
sum += nums[j];
if (sum == k)
ans++;
}
}
return ans;
}
};O(n) 前缀和 + 哈希
回顾 map👇
size/empty/clear //元素个数，判空，清空
begin / end //指向开始 / 结束位置的指针
insert(x) //将元素x插入集合(x为二元组)
erase(x) //删除所有等于x的元素(x为二元组)
erase(it) //删除it指向的元素(it为指向二元组的迭代器)
find(k) //查找键为k的二元组的位置, 若不存在, 返回尾指针 .end()h[key] = val;
//等价于
h.insert(make_pair(key, val));map<string, int>mp;
string s;
for(int i = 0; i < n; ++i) {
cin>>s;
mp[s]++; //s就是键, 是类型为string类的字符串
}
cout<<"输入字符串s, 查询该字符串出现的次数: "<<endl;
cin>>s;
cout<<mp[s]<<endl;思路
pre[i] 表示前 i 项和，所以 pre[i] - pre[j - 1] == k 表示 [j, i] 的区间和 满足题目要求
即 pre[i] - k == pre[j - 1]
又因为 j - 1 < i
此时只需要在 for(int i; i < n; ++i) 顺序遍历 的过程中，
统计，有多少个之前的前缀和 pre[j - 1]， 满足当前的 pre[i] - k
只需要建立 (键--pre[i] - k) (值--出现次数) 的哈希表
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n = nums.size();
unordered_map<int, int> mp;
mp[0] = 1; // 表示 pre - k == 0, 即当前前缀和 == k, 初始状态
int ans = 0, pre = 0;
for (int i = 0; i < n; ++i) {
pre += nums[i]; // 当前前缀和
if (mp.find(pre - k) != mp.end())
ans += mp[pre - k];
mp[pre]++;
}
return ans;
}
};🌼滑动窗口最大值
暴力做法，滑动窗口，除了开头 k-1 和结尾 k-1 个数外，每个数都进行了 k 次比较
时间复杂度 O(n * k)，题目中 n = 1e5，k = 1e5，1e10会TLE（一般1e8以内）
O(nlogn) 优先队列
补充
1）关于优先队列👇（目录--priority_queue）
2）priority_queue 中的 .emplace()👇
std::priority_queue<T,Container,Compare>::emplace - cppreference.com
思路
利用优先队列，最大值在堆顶的特点
优先队列元素为 <num, index> 二元组
使用 .emplace() 或 .push(make_pair()) 插入二元组
对于脱离了滑动窗口，这个区间的元素进行判断
只需对堆顶元素进行 while()
q.top().second <= i - k
就 pop()
优先队列插入元素 O(logn)，遍历一次 O(n)，总的时间复杂度 O(nlogn)
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
// 最小值优先队列
// priority_queue<int, vector<int>, greater<int> >
// 默认堆顶最大值
priority_queue<pair<int, int> > q; // <num, index>
vector<int> ans;
// 处理开头 0~k-1
for (int i = 0; i < k; ++i)
q.emplace(nums[i], i);
// q.push(make_pair(nums[i], i)); // 等价
ans.push_back(q.top().first); // 插入堆顶最大值
// 循环处理后续的
for (int i = k; i < nums.size(); ++i) {
q.emplace(nums[i], i); // 插入二元组
while (q.top().second <= i - k) // 堆顶元素不在滑动窗口内
q.pop();
ans.push_back(q.top().first); // 插入当前窗口最大值
}
return ans;
}
};O(n) 单调队列
关于 deque👇点击目录
坑
明确 deque<int> q 存的是索引，所以 q.front()，q.back() 也是索引
值的话，用 nums[q.front] 和 nums[q.back()] 表示
思路
利用单调队列有序的特点，用 deque 实现一个递减的单调队列，队头一直是最大值，队尾一直是最小值
遍历第 0 ~ k-1 个元素，队列非空 && 当前值 >= 队尾，就 pop 队尾，因为队尾一定是 deque 的最小值
pop 完毕后，当前索引 i 插入 deque
接着遍历后面的元素，重复上述操作，多了一步，对超出滑动窗口范围元素的 pop
即，滑动窗口左边界再往左的元素
由于元素只会在队尾插入 push_back，所以队头 q.front() 索引，一定是最小的
if (q.front() <= i - k) 即可
遍历一遍 O(n)，插入 O(1)，为什么插入 O(1) 呢，因为这里用 deque 双端队列模拟的单调队列，每次插入元素，会通过 while 将队尾 <= 当前元素的，全部 pop，而可以 pop 的总数是有限的，一共 n 个，常数复杂度，因而不会叠加到遍历的 O(n) 里，最终就是 O(n) * O(1)
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
deque<int> q;
vector<int> ans;
// 处理前 k 个元素
for (int i = 0; i < k; ++i) {
while (!q.empty() && nums[i] >= nums[q.back()]) // 保证队尾索引对应的值最小
q.pop_back(); // pop 前一定要 非空
q.push_back(i); // 最小值的索引，插入队尾
}
ans.push_back(nums[q.front()]); // 当前最大值插入答案数组
// 处理后面的元素
for (int i = k; i < n; ++i) {
while ( !q.empty() && nums[i] >= nums[q.back()] )
q.pop_back();
q.push_back(i);
// 去掉滑动窗口范围外的元素
while (q.front() <= i - k) // 索引
q.pop_front();
// 当前最大值插入 ans
ans.push_back(nums[q.front()]);
}
return ans;
}
};O(n) 分块 + 预处理
关键：前后缀数组，只针对当前分好组的窗口来确定最大值，所有逻辑都是以这个为前提
思路
0）先分块，将整个区间，分成若干块，比如，n = 10，k = 3，
分成 0 1 2 3 4 5 6 7 8 9，一共四块
然后开始预处理👇
i 表示滑动窗口第一个元素，i + k - 1 表示最后一个元素，得到区间 [i, i + k -1]
1）我用 left_max 和 right_Max 作为前后缀数组（更直观），代替题解中的 prefixMax 和 suffixMax
2）当 i 不是 k 的倍数，即滑动窗口第一个元素，不是分块的第一个元素，那么窗口必然横跨两个分块，分两部分讨论
[i, j - 1] 和 [j, i + k - 1]
根据这个思路，即可 预处理 前缀 和 后缀 数组
前缀数组 left_Max[i] 表示当前分块内，从 i 开始，往左所有元素的最大值
后缀数组 right_Max[i] 表示当前分块内，从 i 开始，往右的最大值
后续具体逻辑，画图分析，分别预处理 前后缀数组，分 i 是否是 k 的倍数 2 种情况讨论即可
3）为什么前缀数组 0~n-1 预处理，后缀数组要反过来呢👇
类似 dp 一样
前缀数组，要先预处理前面的，后面的以前面的为基础
....
前缀数组 left_Max 找最大值，要在当前分块往左找
后缀数组 right_Max，要在当前分块往右找
4）还有对边界的讨论，
前缀的边界就是 i == 0，nums[0] == left_Max[0] 包含在 if (i % k == 0) 里，不用特殊处理
后缀的边界是 i == n -1，画图发现，未包含在 if (i % k == 0) 里，所以需要加个条件
&& i == n - 1
5）坑
vector<int> left_Max(n), right_Max(n); // 记得初始化大小
AC 代码
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
// 前缀 / 后缀数组（只针对当前分好组的窗口）
vector<int> left_Max(n), right_Max(n); // 记得初始化大小
// 预处理前缀数组
for (int i = 0; i < n; ++i) {
if (i % k == 0) // 分块第一个元素作为结尾
left_Max[i] = nums[i];
else
// 否则，取当前元素开始，往左直到分块第一个元素，的最大值
left_Max[i] = max(nums[i], left_Max[i - 1]);
}
// 预处理后缀数组
for (int i = n - 1; i >= 0; --i) {
// 分块最后一个元素作为开头 或 最后一个元素（建议画图）
if ( (i + 1) % k == 0 || i == n - 1)
right_Max[i] = nums[i];
else
right_Max[i] = max(nums[i], right_Max[i + 1]);
}
// 后缀 right_Max[i] 开头, 前缀 left_Max[i + k - 1] 结尾
vector<int> ans;
for (int i = 0; i <= n - k; ++i)
ans.push_back( max(right_Max[i], left_Max[i + k - 1]) );
return ans;
}
};🌼最小覆盖子串
O(m + n) 滑动窗口 + 变量
力扣官方题解的视频，讲的很好，可以看看 18 分钟之前的，尤其是代码讲解部分
前言
本题类似 “字符串中所有字母异位词” 这道题👇
438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
这道题的第一种做法是 滑动窗口 + 桶
第二种对滑动窗口的优化，就采用了一个变量 differ 来统计，字符串 p 和 滑动窗口，
数量不同字母的个数
而本题呢，采用 distance 来表示，滑动窗口覆盖了多少个字符串 t 中的字符，就是如果可以逐个抵消完 字符串 t 的字符，就满足覆盖的条件
std::basic_string<CharT,Traits,Allocator>::substr - cppreference.com
思路
代码注释很详细了！（先处理右指针，覆盖 t 中全部字符后，再处理左指针）
这个比官方的文字题解快很多
统计 字符串t 字符出现次数 O(n)，while 循环，左指针 / 右指针，最多均移动 m 次
总的时间复杂度 O(m + n)
一刷
class Solution {
public:
string minWindow(string s, string t) {
int m = s.size(), n = t.size();
if (m < n || m == 0 || n == 0) return ""; // 特判
// 窗口 和 字符串t 中，每个字符出现的次数
int win_num[150] = {0}, t_num[150] = {0};
// 字符串t 每个字符出现次数
for (int i = 0; i < n; ++i)
t_num[t[i]]++; // t[i] 隐式转换 ASCII值
int l = 0, r = 0; // 滑动窗口 [l, r]
int distance = 0, ans_pos, ans_len = m + 1; // distance 窗口覆盖 t 中字符的数量
while (r < m) {
// 确定右边界
if (t_num[s[r]] == 0) { // 右边界字符不在 t 中
r++;
continue;
}
// 此时，s[r] 是 字符串t 中字符
if (t_num[s[r]] > win_num[s[r]]) // 覆盖数可加
distance++; // 覆盖数 +1
win_num[s[r]]++; // 该字符数量 +1
r++;
// 右边界已确定
// 全部覆盖后，处理 左指针 l
while (distance == n) { // 照抄上面处理右指针的逻辑，略微修改
if (t_num[s[l]] == 0) { // 左边界字符不在 t 中
l++;
continue;
}
// 此时，s 的窗口刚刚好 cover 了 t
if (ans_len > r - l) { // 处理返回值
ans_len = r - l; // 长度（r 已经右移到下一位置，不用 +1）
ans_pos = l; // 起点
}
// 此时，s 的窗口刚刚好 cover 了 t
// 此时，s[l] 是 字符串t 的字符
if (t_num[s[l]] == win_num[s[l]]) // 个数相等时 l 右移
distance--; // 覆盖l数 -1
win_num[s[l]]--; // 该字符数量 -1
l++;
}
}
if (ans_len > m) return ""; // 没有覆盖子串
return s.substr(ans_pos, ans_len);
}
};二刷：2025/1/16 22:55
// 滑动窗口覆盖了多少个 t 中的字符
class Solution {
public:
string minWindow(string s, string t) {
int m = s.size(), n = t.size();
// 特判
if (m == 0 || n == 0 || m < n)
return "";
int l = 0, r = 0, ans_pos = 0, ans_len = m + 1; // 滑动窗口 [l, r]
int cover = 0; // 窗口中覆盖 t 的数量
int win_num[150] = {0}, t_num[150] = {0}; // 窗口字符出现次数, t 串字符出现次数
// t 中字符出现次数
for (int i = 0; i < n; ++i)
t_num[t[i]]++; // 隐式转换, 字符在数组索引中自动转化为 ASCII 值
while (r < m) {
// 右边界字符不在 t 中
if (t_num[s[r]] == 0) {// 不能用 while, 防止s, t都是单个字符死循环
r++;
continue;
}
// 此时窗口右边界 r 在 t 中
// 下一步是让 cover == n, 保证全覆盖
if (t_num[s[r]] > win_num[s[r]]) // 否则可能已经 ==
cover++;
win_num[s[r]]++;
r++; // 移动到下一位置
while (cover == n) { // 已经全覆盖
// 缩小左边界范围
if (t_num[s[l]] == 0) { // 不能用 while
l++;
continue;
}
// 此时恰好满足最小覆盖子串
// 更新答案
if (ans_len > r - l) {
ans_len = r - l;
ans_pos = l;
}
// 继续后续遍历
// 此时恰好满足最小覆盖子串
if (t_num[s[l]] == win_num[s[l]]) // 有可能中间有重复的字符, 导致 win_num[s[l]] > t_num[s[l]]
cover--;
win_num[s[l]]--; // 先窗口-
l++; // 再移动 l 到下一位置
}
}
if (ans_len > m)
return "";
return s.substr(ans_pos, ans_len);
}
};官方题解，还给出一种复杂度稍微高一点的，用哈希表 unordered_map<char, int> 存 window 和 子串 t 各个字符出现次数，判断完全覆盖时，遍历 字符串 t 字符个数的 哈希表
而上面，只需借助一个变量 distance，表示 滑动窗口覆盖了多少个 t 中字符，就能将复杂度优化到 O(m + n)，这种是 “加法” 的思想，当然，相对应还有 “减法” 的思想
三刷：2025/6/2
时间 O(m), 空间 O(k)，m 是字符串 s 的长度，k 是字符集数量 256
class Solution {
public:
string minWindow(string s, string t) {
std::unordered_map<char, int> sNeed, tNeed; // s 窗口 和 t 中的字符数量
int m = s.size(), n = t.size();
for (auto x : t)
tNeed[x]++; // 统计 t 中字符数量
int l = 0, r = 0, ans_pos = 0, ans_len = INT_MAX; // 滑动窗口
int cover = 0; // 已覆盖的数量
while (r < m) {
// 1, 先移动右指针, 直到所有字符都包括在内
if (tNeed[s[r]] == 0) { // t 中找不到当前字符
r++;
continue;
}
if (sNeed[s[r]] < tNeed[s[r]])
cover++;
sNeed[s[r]]++; // 当前字符++
r++; // 移动下一位置
// 2, 所有字符包括在内后, 处理后续逻辑
while (cover == n) {
// 先移动左指针, 去掉不在 t 中的字符
while (tNeed[s[l]] == 0)
l++;
// 更新最小窗口
if (ans_len > r - l) {
ans_len = r - l;
ans_pos = l;
}
// 3, 缩小左边界
if (sNeed[s[l]] == tNeed[s[l]])
cover--;
sNeed[s[l]]--;
l++;
}
}
return ans_len == INT_MAX ? "" : s.substr(ans_pos, ans_len);
}
};
扫一扫
591
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
