滑动窗口
滑动窗口
209. 长度最小的子数组
int min(int a, int b) {
return a > b ? b : a;
}
int minSubArrayLen(int target, int *nums, int numsSize) {
int res = 0x7fffffff;
for (int l = 0, r = 0, sum = 0; r < numsSize; r++) {
// 查看以nums[r]结尾的子数组中是否有符合条件的
sum += nums[r];
// 尽量减小以nums[r]结尾的子数组长度
while (sum - nums[l] >= target) {
sum -= nums[l];
l++;
}
// 记录所有位置结尾中的最短数组
if (sum >= target) res = min(res, r - l + 1);
}
return res == 0x7fffffff ? 0 : res;
}
3. 无重复字符的最长子串
int max(int a, int b) {
return a > b ? a : b;
}
int lengthOfLongestSubstring(char *s) {
int len = strlen(s);
if (len < 2) return len;
// 记录字符是否在当前窗口中
int *hashSet = (int *) calloc(128, sizeof(int));
int left = 0, right = 0;
hashSet[s[right]] = 1;
int res = 1;
while (right + 1 < len) {
// 待进入窗口的下个字符
char nextChar = s[right + 1];
if (hashSet[nextChar] == 0) {
// 未出现过就加入到窗口中
hashSet[nextChar] = 1;
right++;
// 更新最大长度
res = max(res, right - left + 1);
} else {
// 已经出现在窗口中，就移动left，去掉left之前的字符
while (left <= right && s[left] != nextChar) {
hashSet[s[left]] = 0;
left++;
}
// 此时s[left]和nextChar相等，窗口整体右移一格，相当于从窗口中删除s[left]
left++;
right++;
}
}
return res;
}
int max(int a, int b) {
return a > b ? a : b;
}
int lengthOfLongestSubstring(char *s) {
int len = strlen(s);
int res = 0;
// 记录每个字符上次出现的位置
int last[128];
memset(last, -1, sizeof(int) * 128);
for (int l = 0, r = 0; r < len; r++) {
// 更新窗口左边界
l = max(l, last[s[r]] + 1);
// 记录最大窗口长度
res = max(res, r - l + 1);
// 更新当前字符最后一次出现的位置
last[s[r]] = r;
}
return res;
}
76. 最小覆盖子串
// 题目默认如果存在则唯一
char *minWindow(char *s, char *t) {
int lenS = strlen(s);
int lenT = strlen(t);
if (lenS < lenT) {
char *res = "";
return res;
}
// 负数表示t中字符在s中需要出现的次数，其他的表示其他字符在s中出现的次数
int map[256] = {0};
for (int i = 0; i < lenT; ++i) map[t[i]]--;
// 最小覆盖子串的长度
int len = 0x7fffffff;
// 最小覆盖子串的起始下标
int start = 0;
// 需要出现的各个字符的总个数
int count = lenT;
for (int r = 0, l = 0; r < lenS; ++r) {
// 是t中的字符，则出现总次数减一
if (map[s[r]] < 0) count--;
// 当前字符出现次数加一
map[s[r]]++;
// 窗口已经包含t中所有字符，即s中已经出现了覆盖子串
if (count == 0) {
// 大于0说明可以从窗口左边移除，从而缩小窗口大小
// 小于等于0时不能移除，否则就凑不齐t中的字符
while (map[s[l]] > 0) {
map[s[l]]--;
l++;
}
if (r - l + 1 < len) {
// 记录窗口大小
len = r - l + 1;
// 记录窗口起始位置
start = l;
}
}
}
if (len == 0x7fffffff) {
char *res = "";
return res;
} else {
char *res = (char *) malloc(sizeof(char) * (len + 1));
res[len] = '\0';
for (int i = 0; i < len; ++i) res[i] = s[start++];
return res;
}
}
134. 加油站
// O(n^2)超时
int canCompleteCircuit(int *gas, int gasSize, int *cost, int costSize) {
// 从每个位置开始尝试
for (int i = 0; i < gasSize; ++i) {
// 站点数
int count = gasSize;
// 出发点
int pos = i;
// 当前油量
int cur = 0;
while (count > 0) {
// 先加上油
cur += gas[pos];
// 油量不够到下个加油站
if (cost[pos] > cur) break;
// 消耗汽油到下个加油站
cur -= cost[pos];
pos = (pos + 1) % gasSize;
count--;
}
if (count == 0) return i;
}
return -1;
}
// O(n^2)超时
int canCompleteCircuit(int *gas, int gasSize, int *cost, int costSize) {
int arr[gasSize];
// 记录余量
for (int i = 0; i < gasSize; ++i)
arr[i] = gas[i] - cost[i];
// 从每个位置开始尝试
for (int i = 0; i < gasSize; ++i) {
// 站点数
int count = gasSize;
// 出发点
int pos = i;
// 余量前缀和
int prefix = 0;
while (count > 0) {
// 先加上油
prefix += arr[pos];
// 油量不够到下个加油站
if (prefix < 0) break;
// 消耗汽油到下个加油站
pos = (pos + 1) % gasSize;
count--;
}
if (count == 0) return i;
}
return -1;
}
// O(n^2)超时
int canCompleteCircuit(int *gas, int gasSize, int *cost, int costSize) {
// 从每个位置开始尝试
for (int i = 0; i < gasSize; ++i) {
// 站点数
int count = gasSize;
// 出发点
int pos = i;
// 余量前缀和
int prefix = 0;
while (count > 0) {
// 余量
prefix += gas[pos] - cost[pos];
// 油量不够到下个加油站
if (prefix < 0) break;
// 消耗汽油到下个加油站
pos = (pos + 1) % gasSize;
count--;
}
if (count == 0) return i;
}
return -1;
}
// O(n)
int canCompleteCircuit(int *gas, int gasSize, int *cost, int costSize) {
// 余量前缀和
int prefixSum = 0;
// 当前窗口大小
int len = 0;
// 从每个位置开始尝试
for (int left = 0, right; left < gasSize; ++left) {
while (prefixSum >= 0) {
if (len == gasSize) return left;
// 计算窗口右边界
right = (left + len) % gasSize;
// 窗口扩大，right移入窗口
len++;
prefixSum += gas[right] - cost[right];
}
// 窗口缩小，left移除窗口
len--;
prefixSum -= gas[left] - cost[left];
}
return -1;
}
1234. 替换子串得到平衡字符串
int min(int a, int b) {
return a > b ? b : a;
}
bool ok(int *counts, int len, int require) {
for (int i = 0; i < 4; ++i) {
// 窗口外的字符频率若超过require，则无法消去多出来的字符
if (counts[i] > require) return false;
// 用长度len的窗口补齐每个字符缺失的个数require - counts[i]
len -= require - counts[i];
}
// 窗口刚好用完
return len == 0;
}
int balancedString(char *s) {
int lenS = strlen(s);
// 最多调整整个数组
int res = lenS;
// 每种字符必须出现的次数
int require = lenS / 4;
// Q W E R转换成0123
int arr[lenS];
// 统计窗口外字符出现次数
int counts[4] = {0};
for (int i = 0; i < lenS; ++i) {
arr[i] = s[i] == 'Q' ? 0 : (s[i] == 'W' ? 1 : (s[i] == 'E' ? 2 : 3));
counts[arr[i]]++;
}
// 窗口[l, r)
for (int l = 0, r = 0; l < lenS; ++l) {
while (!ok(counts, r - l, require) && r < lenS) {
// 窗口右边移入，移入的字符在counts中的计数减一
counts[arr[r]]--;
r++;
}
if (ok(counts, r - l, require))
res = min(res, r - l);
// 窗口左边移出，移出的字符在counts中的计数加一
counts[arr[l]]++;
}
return res;
}
992. K 个不同整数的子数组
int counts[20001];
// 返回nums的所有子数组中，数字种类不超过k的子数组个数
int lower(int *nums, int numsSize, int k) {
memset(counts, 0, sizeof(int) * 20001);
int res = 0;
for (int l = 0, r = 0, types = 0; r < numsSize; r++) {
// 窗口右侧移入nums[r]
// 种类数加一
if (counts[nums[r]] == 0) types++;
// 词频加一
counts[nums[r]]++;
// 种类数超过了，需要从窗口左侧移除
while (types > k) {
// 词频减一
counts[nums[l]]--;
// 刚好把这个字符全部移除
if (counts[nums[l]] == 0) types--;
l++;
}
res += r - l + 1;
}
return res;
}
int subarraysWithKDistinct(int *nums, int numsSize, int k) {
return lower(nums, numsSize, k) - lower(nums, numsSize, k - 1);
}
395. 至少有 K 个重复字符的最长子串
int max(int a, int b) {
return a > b ? a : b;
}
int longestSubstring(char *s, int k) {
int len = strlen(s);
int counts[256];
int res = 0;
// 至少有require个重复字符的最长子串
for (int require = 1; require < 256; ++require) {
memset(counts, 0, sizeof(int) * 256);
// 窗口中字符种类总数
int types = 0;
// 窗口中字符出现次数大于等于k的种类总数
int satisfy = 0;
for (int l = 0, r = 0; r < len; r++) {
counts[s[r]]++;
// 新出现了一个种类
if (counts[s[r]] == 1) types++;
// 新达标了一个种类
if (counts[s[r]] == k) satisfy++;
// 字符种类超了，开始移除左边字符
while (types > require) {
if (counts[s[l]] == 1) types--;
if (counts[s[l]] == k) satisfy--;
// 窗口左侧移出字符
counts[s[l]]--;
l++;
}
// 子串以r位置结尾，且种类总数不超过require的最大长度
if (satisfy == require) res = max(res, r - l + 1);
}
}
return res;
}
热门相关：混在三国当军阀 君归矣 士子风流 名门贵妻：暴君小心点 唐朝小官人