子串
子串
力扣第四个小专题，与其说这是一种算法，倒不如说是一种题型
和为K的子数组
力扣题目连接：和为K的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2示例 2：
输入：nums = [1,2,3], k = 3
输出：2这个题目最先想到的，一定就是暴力枚举，时间复杂度为O(n^2)，显然这样时间复杂度是很大的
可以换用另一种思路：前缀和+哈希表
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int,int> mp;
int count = 0;
int pre = 0;
mp[0]=1; //初始前缀和为0的个数为1：
//nums = [1, 2, 3], k = 3
// 在第一次迭代时：
// 当前前缀和 pre = 3（1+2）
// 为了找 pre - k = 0，我们查看 mp[0]，如果存在就说明有一段从开头开始的子数组和为 k
// 如果我们没有先设置 mp[0] = 1，那么这段子数组（从第一个元素开始）就会被漏掉
for(int x:nums){
pre+=x;
if(mp.find(pre-k)!=mp.end()){
count+=mp[pre-k];
}
mp[pre]++;
}
return count;
}
};滑动窗口最大值
力扣题目连接：滑动窗口最大值
给你一个整数数组 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]思路：
// class Solution {
// public:
// vector<int> maxSlidingWindow(vector<int>& nums, int k) {
// priority_queue<pair<int,int>> q;
// for(int i=0;i<k;i++){
// q.emplace(nums[i],i);
// }
// vector<int> result={q.top().first};
// for(int i=k;i<nums.size();i++){
// q.emplace(nums[i],i);
// while(q.top().second<=i-k){
// q.pop();
// }
// result.push_back(q.top().first);
// }
// return result;
// }
// };
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
deque<int> q;
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;
}
};最小覆盖子串
力扣题目连接：最小覆盖子串
给你一个字符串 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 的子串中，
因此没有符合条件的子字符串，返回空字符串。
思路：题目中要求返回最小覆盖子串，首先想到的便是使用滑动窗口，然后移动窗口，当窗口中的字符满足要求时，记录最小覆盖子串的起始位置和长度。但是这里面有一些细节问题需要思考，比如如何移动窗口，以及如何判断窗口中的字符是否满足要求，满足要求后如何确定最小覆盖子串的起始位置和长度。这里使用哈希表来记录窗口中的字符，以及窗口中字符的个数。当窗口中的字符个数满足要求时，判断当前窗口的长度是否小于最小覆盖子串的长度，如果小于则更新最小覆盖子串的起始位置和长度。
class Solution {
// 初始化两个哈希表
Map<Character, Integer> ori = new HashMap<>();
Map<Character, Integer> cnt = new HashMap<>();
public String minWindow(String s, String t) {
int tLen = t.length();
// 初始化 t 中的哈希表
for (char c : t.toCharArray()) {
ori.put(c, ori.getOrDefault(c, 0) + 1);
}
// 初始化滑动窗口
int l = 0, r = -1;
// len表示最小覆盖子串的长度
int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
while (r < s.length()) {
// 移动窗口的右边界
++r;
// 如果当前字符在 t 中出现，则更新 cnt 中的对应字符的个数
if (r< s.length() &&ori.containsKey(s.charAt(r))) {
cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
}
// 判断窗口中的字符是否满足要求
while (check() && l <= r) {
if (r - l + 1 < len) {
len = r - l + 1;
ansL = l;
ansR = l + len - 1;
}
if (ori.containsKey(s.charAt(l))) {
cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
}
++l;
}
}
// 返回最小覆盖子串，注意这里的substring的参数是左闭右开
return ansL == -1 ? "" : s.substring(ansL, ansR + 1);
}
// 判断窗口中的字符是否满足要求
private boolean check() {
// 注意entrySet()返回的是一个Set<Map.Entry<K,V>>
for (Map.Entry<Character, Integer> entry : ori.entrySet()) {
Character key = entry.getKey();
Integer value = entry.getValue();
if (cnt.getOrDefault(key, 0) < value) {
return false;
}
}
return true;
}
}