先填坑
滑动窗口
3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
思路：用一个uset容器存放当前滑动窗口中的元素
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> str;
int left = 0,right = 0;
int maxLen = 0;
for(;right < s.size(); right++) {
while(left < right && str.count(s[right])) {
str.erase(s[left++]);
}
maxLen = max(right - left + 1, maxLen);
str.insert(s[right]);
}
return maxLen;
}
};
438. 找到字符串中所有字母异位词是
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
思路:先用vector数组把p存起来，然后遍历s，记滑动窗口右边界为r，则cnt[s[r] - a] < 0，滑动窗口左边界l右移cnt[s[l] - a] ++；
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> cnt(26, 0);
vector<int> res;
for(char c : p) {
cnt[c - 'a']++;
}
int l = 0, r = 0;
while(r < s.size()) {
cnt[s[r] - 'a']--;
r++;
while(cnt[s[r - 1] - 'a'] < 0){
cnt[s[l] - 'a']++;
l++;
}
if(r - l == p.size()) {
res.push_back(l);
}
}
return res;
}
};
子串
560. 和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
前缀和+哈希，用unordered_map<前缀和， 出现次数> umap来存储前缀和，则符合条件的[i, j] 满足pre[j]-pre[i-1] == k;遍历nums[i] ，求和umap[pre - k]
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> umap;
umap[0] = 1;
int pre = 0, count = 0;
for(int i = 0; i < nums.size();