滑动窗口
滑动窗口：维持左、右边界都不回退的一段范围，来求解很多子数组（串）的相关问题
滑动窗口的关键：找到 范围 和 答案指标 之间的 单调性关系（类似贪心）
滑动过程：滑动窗口可以用 简单变量 或者 结构 来 维护信息
求解大流程：求子数组在 每个位置 开头 或 结尾 情况下的答案（开头还是结尾在于个人习惯）
长度最小的子数组 累加和大于等于target的最短子数组长度 给定一个含有 n 个正整数的数组和一个正整数 target 找到累加和 >= target 的长度最小的子数组并返回其长度 如果不存在符合条件的子数组返回0
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int L = 0, R = 0;
int sum = 0;
int ans = nums.size()+1;
while (R <= nums.size() - 1) {
sum += nums[R];
while (sum - nums[L] >= target) {
sum -= nums[L];
L++;
}
if(sum >= target)
ans = min(ans, R - L + 1);
R++;
}
if(ans == nums.size() + 1) ans = 0;
return ans;
}
};
无重复字符的最长子串 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
关键是左区间的单调性，不可能往回缩只能往前，用一个数组维护每个字符上次出现的位置
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int loc[128];
for(int i = 0; i < 128; i++) loc[i] = -1;
int ans = 0;
int n = s.size();
for(int l = 0,r = 0; r < n; r++) {
int c = s[r];
l = max(l,loc[c]+1);
loc[c] = r;
ans = max(ans,r - l +1);
}
return ans;
}
};
加油站 在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车， 从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升 你从其中的一个加油站出发，开始时油箱为空。 给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周 则返回出发时加油站的编号，否则返回 -1 如果存在解，则 保证 它是 唯一 的。
用滑动窗口把直接暴力的时间复杂度从O(n^2) 降到 O(n) 引入长度方便表示，下标为0的数组方便循环取余。 r = (l + (++len)) % n;
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size();
for (int l = 0, r = 0, len = 0, sum = 0; l < n; l++) {
while (sum >= 0) {
if (len == n) {
return l;
}
sum += gas[r] - cost[r];
r = (l + (++len)) % n;
}
len--;
sum -= gas[l] - cost[l];
}
return -1;
}
};
替换子串得到平衡字符串 有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。
假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。
给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
请返回待替换子串的最小可能长度。
如果原字符串自身就是一个平衡字符串，则返回 0。
class Solution {
public:
int balancedString(string s) {
map<char, int> mp;
for (auto& x : s) {
mp[x]++;
}
int n = s.size();
int ans = n;
map<char, int> mp2;
for (int l = 0, r = 0; r < n; r++) {
mp2[s[r]]++;
while (l <= r && mp2[s[l]] > mp[s[l]] - n / 4) {
mp2[s[l]]--;
l++;
}
bool ok = true;
for (auto& [k, v] : mp) {
if (v - mp2[k] > n / 4) {
ok = false;
break;
}
}
if (ok) {
ans = min(ans, r - l + 1);
}
}
return ans;
}
};
给定一个正整数数组 nums和一个整数 k，返回 nums 中 「好子数组」 的数目。
如果 nums 的某个子数组中不同整数的个数恰好为 k，则称 nums 的这个连续、不一定不同的子数组为 「好子数组 」。
例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。 子数组 是数组的 连续 部分。
恰好求k个数比较麻烦，转换一下等于 小于等于k的子数组数量 - 小于等于k-1的子数组数量 因为找到一个边界恰好等于k,其中l - r 的子数组都是小于等于k个
class Solution {
public:
int less_than_k(vector<int>& nums, int k) {
int n = nums.size();
int cur = 0;
map<int, int> mp;
int ans = 0;
for (int l = 0, r = 0; r < n; r++) {
if (++mp[nums[r]] == 1) {
cur++;
}
while (cur > k && l <= r) {
if (--mp[nums[l]] == 0)
cur--;
l++;
}
ans += r - l + 1;
}
return ans;
}
int subarraysWithKDistinct(vector<int>& nums, int k) {
return less_than_k(nums,k) - less_than_k(nums, k - 1);
}
};
至少有k个字符的最长子串 给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
如果不存在这样的子字符串，则返回 0。
分析，把问题分解成恰好含有i种字符的最长子串，最多求26遍，取其中最大值
class Solution {
public:
int longestSubstring(string s, int k) {
int ans = 0;
int n = s.size();
int fre[26];
int cur,satis;
for (int i = 1; i <= 26; i++) {
memset(fre, 0, sizeof(fre));
cur = 0, satis = 0;
for (int l = 0, r = 0; r < n; r++) {
fre[s[r] - 'a']++;
if (fre[s[r] - 'a'] == 1)
cur++;
if (fre[s[r] - 'a'] == k)
satis++;
while (cur > i && l <= r) {
fre[s[l] - 'a']--;
if (fre[s[l] - 'a'] == 0)
cur--;
if (fre[s[l] - 'a'] == k-1)
satis--;
l++;
}
if(satis == i) ans = max(ans,r-l+1);
}
}
return ans;
}
};