- 滑动窗口的核心在于
- 不能回头,互动窗口只能向前滑动
- 题目一般要求是连续的,类似子串,不能是子序列
给定一个字符串 `s` ，请你找出其中不含有重复字符的 **最长子串** 的长度。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<int, int> hashMap;
int result=0,now=-1;
for (int i = 0; i < s.size(); i++) {
if (hashMap.find(s[i])!=hashMap.end()) {
now=max(now,hashMap[s[i]]);
}
hashMap[s[i]]=i;
result=max(i-now,result);
}
return result;
}
};
给你一个字符串 `s` 、一个字符串 `t` 。返回 `s` 中涵盖 `t` 所有字符的最小子串。如果 `s` 中不存在涵盖 `t` 所有字符的子串，则返回空字符串 `""` 。
**注意：**
- 对于 `t` 中重复字符，我们寻找的子字符串中该字符数量必须不少于 `t` 中该字符数量。
- 如果 `s` 中存在这样的子串，我们保证它是唯一的答案。
给定两个字符串 `s` 和 `p`，找到 `s` 中所有 `p` 的 **异位词** 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
**异位词** 指由相同字母重排列形成的字符串（包括相同的字符串）。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int sLen = s.size(), pLen = p.size();
if (sLen < pLen) {
return vector<int>();
}
vector<int> ans;
vector<int> sCount(26);
vector<int> pCount(26);
for (int i = 0; i < pLen; ++i) {
++sCount[s[i] - 'a'];
++pCount[p[i] - 'a'];
}
if (sCount == pCount) {
ans.emplace_back(0);
}
for (int i = 0; i < sLen - pLen; ++i) {
--sCount[s[i] - 'a'];
++sCount[s[i + pLen] - 'a'];
if (sCount == pCount) {
ans.emplace_back(i + 1);
}
}
return ans;
}
};
给你一个整数数组 `nums` 和一个整数 `k` ，请你返回子数组内所有元素的乘积严格小于 `k` 的连续子数组的数目。
- 一个简单的思路是二分搜索O(nlog(n))
- 滑动窗口O(n)
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
int n = nums.size(), ret = 0;
int prod = 1, i = 0;
for (int j = 0; j < n; j++) {
prod *= nums[j];
while (i <= j && prod >= k) {
prod /= nums[i];
i++;
}
ret += j - i + 1;
}
return ret;
}
};
给定两个字符串 `s` 和 `p`，找到 `s` 中所有 `p` 的 **异位词** 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
**异位词** 指由相同字母重排列形成的字符串（包括相同的字符串）。
- 构造长度为len(p)的滑动窗口,遍历时候循环检查一下26个字母是否每个都匹配
定一个字符串 `s` 和一个字符串数组 `words`**。** `words` 中所有字符串 **长度相同**。
`s` 中的 **串联子串** 是指一个包含 `words` 中所有字符串以任意顺序排列连接起来的子串。
- 例如，如果 `words = ["ab","cd","ef"]`， 那么 `"abcdef"`， `"abefcd"`，`"cdabef"`， `"cdefab"`，`"efabcd"`， 和 `"efcdab"` 都是串联子串。 `"acdbef"` 不是串联子串，因为他不是任何 `words` 排列的连接。
返回所有串联字串在 `s` 中的开始索引。你可以以 **任意顺序** 返回答案。
- 核心就是滑动窗口,惊艳的点在于使用unordered_map作为统计数量,如果向右滑动就key的val++.左边的key的val--,如果key的val为0就erase,最后如果map为empty说明位置是ok的记录下来
- 如果是和为k,直接前缀和+hash带走,但是这个是最接近,比较有意思
- 最接近分为联合,分别为正向最接近和反向最接近,分辨使用滑动窗口,维护左边能选到的边界
int left=-1;
long long likely=INT32_MAX;
for (int i = 0; i < len; i++) {
now+=arr[i];
if (now<sum) {
continue;
}
while (left<=i&&now-arr[left+1]>=sum) {// 移动左边界保证大于等于目标值的最右边
left++;
now-=arr[left];
}
if (abs(sum-now)<likely) {
likely=abs(sum-now);
}
}
left=-1;
now=0;
for (int i = 0; i < len; i++) {
now+=arr[i];
while (left<=i&&now>sum) {// 移动左边界,保证小于等于的最小左边界
left++;
now-=arr[left];
}
if (abs(sum-now)<likely) {
likely=abs(sum-now);
}
}
几张卡牌 **排成一行**，每张卡牌都有一个对应的点数。点数由整数数组 `cardPoints` 给出。
每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 `k` 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 `cardPoints` 和整数 `k`，请你返回可以获得的最大点数。
- 挺有意思的题目,难点在于将左右两边转换为中间的滑动窗口
- 滑动窗口通常要求连续
- 前缀hash通常只是要求是某个序列
- 滑动窗口不支持向前滑动,只能向后,出现就不能使用滑动窗口