本系列为笔者的 Leetcode 刷题记录，顺序为 Hot 100 题官方顺序，根据标签命名，记录笔者总结的做题思路，附部分代码解释和疑问解答。
目录
01 和为 K 的子数组
方法一：枚举
方法二：前缀和 + 哈希表优化
02 滑动窗口最大值
方法一：优先队列（堆）
方法二：双端队列
方法三：动态规划
03 最小覆盖子串
方法：哈希映射 + 双指针
01 和为 K 的子数组
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
}
};方法一：枚举
-
建立双指针
start和end -
start指向子数组末尾 -
end指向子数组开头 -
从右至左，计算子数组元素之和
sum，判断sum == k
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int count = 0;
for(int start = 0; start < nums.size(); ++start){
int sum = 0;
for(int end = start; end >= 0; --end){
sum += nums[end];
if(sum == k) count++;
}
}
return count;
}
};方法二：前缀和 + 哈希表优化
-
建立哈希数组
mp -
''键'' 存储左边所有元素之和
pre -
''值'' 存储
pre的出现次数mp[pre] -
从左至右，判断
mp.find(pre - k) != mp.end()
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int count = 0;
unordered_map<int, int> mp;
mp[0] = 1; //1 why
int pre = 0;
for(auto& x: nums){
pre += x;
if(mp.find(pre - k) != mp.end()) count += mp[pre - k];
mp[pre]++; //2 重复了怎么办
}
return count;
}
};02 滑动窗口最大值
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
}
};方法一：优先队列（堆）
-
建立有序大根堆
q -
"键" 存储数
-
''值'' 存储位置
-
不断地添加新元素，判断
q.top().second <= (i - k)，执行年龄淘汰
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
priority_queue<pair<int, int>> q; //键存储数，值存储位置
int n = nums.size();
//第一轮遍历
for(int i=0; i<k; i++){
q.emplace(nums[i], i);
}
vector<int> ans = {q.top().first};
//第二轮遍历
for(int i=k; i<n; i++){
q.emplace(nums[i], i);
while(q.top().second <= (i - k)) q.pop(); //年龄淘汰
ans.push_back(q.top().first);
}
return ans;
}
};① priority_queue 是一种基于堆的数据结构，内部实现通常使用最大堆（binary heap），因此元素默认是从大到小排序的。
② pair 是 STL 中一个简单的模板类，用于存储两个数据值，std::pair<int, int> 表示一对整数，在比较两个 pair 类型的元素时，通常根据第一个元素（first）进行比较，如果相同则比较第二个元素（second）。
方法二：双端队列
-
建立双端队列
q，存储位置 -
q中位置严格递增，能力严格递减 -
不断地添加新元素，判断
q.front() <= (i - k)，执行年龄淘汰
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
deque<int> q; //存储位置 front back
for(int i=0; i<k; ++i){
//末位淘汰
while(!q.empty() && nums[i] >= nums[q.back()]) q.pop_back();
q.push_back(i);
}
vector<int> ans = {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.push_back(nums[q.front()]);
}
return ans;
}
};deque 是双端队列（double-ended queue）的缩写，它提供常数时间复杂度的随机访问、在容器两端的插入与删除操作。
方法三：动态规划
-
建立两个数组
prefixMax(n)和suffixMax(n) -
prefixMax[i]记录某个滑动窗口内，i左边最大值 -
-
suffixMax[i]记录某个滑动窗口内，i右边最大值 -
-
滑动窗口滑动中，判断
max(prefixMax[i+k-1], suffixMax[i])
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
vector<int> prefixMax(n);
vector<int> suffixMax(n);
for(int i=0; i<n; ++i){
if(i%k == 0) prefixMax[i] = nums[i];
else prefixMax[i] = max(prefixMax[i-1], nums[i]);
}
for(int i=n-1; i>=0; --i){
if((i+1)%k == 0 || i == n-1) suffixMax[i] = nums[i];
else suffixMax[i] = max(suffixMax[i+1], nums[i]);
}
vector<int> ans;
for(int i=0; i<=n-k; ++i){
ans.push_back(max(prefixMax[i+k-1], suffixMax[i]));
}
return ans;
}
};03 最小覆盖子串
class Solution {
public:
string minWindow(string s, string t) {
}
};方法：哈希映射 + 双指针
-
建立两个哈希映射
unordered_map<char, int> ori, cnt;，ori存储t中元素情况，cnt存储s中t中元素情况 -
建立双指针
l和r，在满足r < int(s.size())的情况下，r用于「延伸」现有窗口；在满足check()的情况下，l用于「收缩」窗口，找寻最短窗口程度len
class Solution {
public:
unordered_map<char, int> ori, cnt;
bool check(){
for(const auto& p: ori){
if(cnt[p.first] < p.second) return false;
}
return true;
}
string minWindow(string s, string t) {
for(const auto& c:t){
++ori[c];
}
int l = 0, r = -1;
int len = INT_MAX, ansL = -1;
while(r < int(s.size())){
++r;
if(ori.find(s[r]) != ori.end()) ++cnt[s[r]]; //「延伸」
while(check() && l <= r){
if((r-l+1) < len){ //版本答案更新
len = r-l+1;
ansL = l;
}
if(ori.find(s[l]) != ori.end()) --cnt[s[l]]; //「收缩」
++l;
}
}
return ansL==-1 ? string() : s.substr(ansL, len);
}
};① string()返回一个默认构造的 std::string 对象，表示没有找到有效结果或不符合条件。
② s.substr(ansL, len) 是一个字符串提取方法，表示提取 s 字符串从索引 ansL 开始、长度为 len 的子串。这个部分用于返回有效的结果字符串。
③ INT_MAX 是一个常量，定义在 C++ 的头文件 <climits> 或 <limits.h> 中。它代表 int 类型能表示的最大值。在标准环境下，INT_MAX 的值通常为 2,147,483,647（即 2^31 - 1）
④ 为什么r < int(s.size())要用int()，s.size()不是本来就是int吗？
s.size() 返回的是 std::string::size_type，这通常是一个无符号整数类型 unsigned long 或 unsigned long long，有时需要将其显式转换为常用的有符号类型（如 int），尤其是在涉及负数计算（如这里的 r 初始为 -1）时，以避免潜在的编译警告或逻辑问题。
⑤ while (check() && l <= r) 这一判断语句中，什么样的情况下满足check()成立但l <= r不成立？
不存在该情况。r 总是从 -1 开始然后逐渐向右移动，l 开始为 0 并仅在满足 check() 的情况下向右移动（l 左移），在正常执行过程中，l > r 的情况实际上是不太可能出现的。
⑥ ansR 是不是没啥用啊，直接扔掉行不？
是的。通常在寻找子串或窗口的时候，记录 ansR 是多余的，因为我们其实只是关心子串的开始位置 ansL 以及其长度 len。
文章部分代码来源于力扣（LeetCode）
