力扣hot100_子串
目录
力扣hot100_子串
hot100_239.滑动窗口最大值
给你一个整数数组
nums
，有一个大小为
k
的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的
k
个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7示例 2：
输入：nums = [1], k = 1
输出：[1]提示：
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
#include<iostream>
#include<vector>
#include<deque>
using namespace std;
class Solution{
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
deque<int> maxqueue;
int len = 0;
for(int i = 0; i < nums.size(); i++){
//将已经退出滑动窗口的元素出队
while(len > 0 && maxqueue.front() < i-k+1){
maxqueue.pop_front();
len--;
}
//维护递减队列
while(len > 0 && nums[maxqueue.back()]<= nums[i]){
maxqueue.pop_back();
len--;
}
maxqueue.push_back(i);
len++;
if(i >= k - 1){
result.push_back(nums[maxqueue.front()]);
}
}
return result;
}
};
int main(){
// vector<int> nums = {1};
vector<int> nums = {1,3,1,2,0,5};
int k = 3;
Solution A;
vector<int> result = A.maxSlidingWindow(nums, k);
for(int i = 0; i < result.size(); i++){
cout << result[i] << " ";
}
cout<<endl;
return 0;
}hot100_560.和为k的子数组
给你一个整数数组
nums
和一个整数
k
，请你统计并返回
该数组中和为
k
的子数组的个数
。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2示例 2：
输入：nums = [1,2,3], k = 3
输出：2提示：
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000`-107 <= k <= 107`
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
class Solution{
public:
int sunarraySum(vector<int>& nums, int k){
unordered_map<int, int> hashMap;
hashMap[0] = 1;
// 记录满足条件的子数组个数
int count = 0;
// 初始化前缀和
int prefixSum = 0;
for (int num : nums) {
// 计算当前的前缀和
prefixSum += num;
// 检查是否存在 prefix_sum - k 的前缀和
if (hashMap.find(prefixSum - k) != hashMap.end()) {
// 加上满足条件的前缀和个数
count += hashMap[prefixSum - k];
}
// 更新哈希表中的当前前缀和出现次数
hashMap[prefixSum]++;
}
return count;
}
};
int main(){
vector<int> nums = {1, 2, 3};
int k = 3;
Solution A;
cout << A.sunarraySum(nums,k) << endl;
return 0;
}hot100_76.最小覆盖子串
给你一个字符串
s
、一个字符串
t
。返回
s
中涵盖
t
所有字符的最小子串。如果
s
中不存在涵盖
t
所有字符的子串，则返回空字符串
""
。
注意：
- 对于t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。
- 如果s中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。示例 2：
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。提示：
m == s.lengthn == t.length1 <= m, n <= 10^5s和t由英文字母组成class Solution{ public: string minWindow(string s, string t) { bool is_t[52] = {false}; bool is_minstr = false; int count[52] = {0}; queue<int> Q; int k = t.length(); int minl=0,minr=10^5+1; int l = 0; for(char a:t){ int index = findIndex(a); is_t[index] = true; count[index]++; } for(int i = 0; i < s.length(); i++){ char a = s[i]; int index = findIndex(a); if(Q.empty()&&!is_t[index]) { l++; continue; } else if(is_t[index] && count[index]==0){ Q.push(index); while(Q.front()!=index) { char tempIndex = Q.front(); count[tempIndex]++; if(is_t[tempIndex]) k++; Q.pop(); l++; } Q.pop(); l++; while(!is_t[Q.front()]) { Q.pop(); l++; } } else if(is_t[index] && count[index] > 0){ Q.push(index); count[index]--; k--; } else{ Q.push(index); } if(k == 0 && i - l < minr - minl){ minr = i; minl = l; is_minstr = true; } // cout << "k = " <<k <<endl; // cout<< "队首元素下标：" << Q.front()<<endl; } // cout << minl << " " << minr<<endl; if(!is_minstr) return ""; else{ string minstr = ""; for(int i = minl; i <= minr; i++){ minstr = minstr + s[i]; } return minstr; } } int findIndex(char a){ int index; if(a<='Z') index = a-'A'; else index = a-'a'+26; return index; } };