about Sliding Window4
Sliding Window pattern in algorithm, 滑动窗口套路
Replace the Substring for Balanced String
和相同的二元子数组
给你一个二元数组nums ，和一个整数goal ，请你统计并返回有多少个和为goal的非空子数组。
子数组是数组的一段连续部分。
示例 1：
输入：nums = [1,0,1,0,1], goal = 2
输出：4
解释：
有 4 个满足题目要求的子数组：[1,0,1]、[1,0,1,0]、[0,1,0,1]、[1,0,1]
示例 2：
输入：nums = [0,0,0,0,0], goal = 0
输出：15
前缀法
Map<Integer, Integer> map = new HashMap<>();
int res = 0;
int sum = 0;
for (int num : nums) {
map.put(sum, map.getOrDefault(sum, 0) + 1);
sum += num;
res += map.getOrDefault(sum - goal, 0);
}
return res;
}
public int numSubarraysWithSum(int[] nums, int goal) {
int[] count = new int[nums.length + 1];
int res = 0;
int sum = 0;
for (int i : nums) {
// 一边加
count[sum]++;
sum += i;
// 一边算
if (sum - goal >= 0) {
res += count[sum - goal];
}
}
return res;
}
那么 L2 与 L1 之间有几个 0，那这个部分就有多少种子数组
同时本题只含有 0 与 1，那么肯定可以保证滑动窗口内的元素和要么等于 goal，要么等于 goal+1
那么我们可以定义：
L1 与 R 直接的窗口内元素为 goal
L2 与 R 直接的窗口内元素为 goal+1
public int numSubarraysWithSum(int[] nums, int goal) {
int left1 = 0, left2 = 0, right = 0, res = 0, sum1 = 0, sum2 = 0;
while (right < nums.length) {
sum1 += nums[right];
while (left1 <= right && sum1 > goal) {
sum1 -= nums[left1++];
}
sum2 += nums[right];
while (left2 <= right && sum2 >= goal) {
sum2 -= nums[left2++];
}
res += left2 - left1;
right++;
}
return res;
}
K 个不同整数的子数组
给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定不同的子数组为好子数组。
（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）
返回 A 中好子数组的数目。
示例 1：
输入：A = [1,2,1,2,3], K = 2
输出：7
解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
示例 2：
输入：A = [1,2,1,3,4], K = 3
输出：3
解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].
核心是一手：恰好转化为最多之差
最多包含 K 个不同整数的子数组，意即包含 1,2… K 个 不同整数的子数组皆在此列
如此，最多包含 K 个不同整数的子数组个数即恰好包含 1,2..K 个不同整数的子数组个数，而最多包含 K-1 个不同整数的子数组个数即恰好包含 1,2… K-1 个不同整数的子数组个数
两者相减即为恰好包含 K 个不同整数的子数组个数
public int subarraysWithKDistinct(int[] nums, int k) {
return atMost(nums, k) - atMost(nums, k - 1);
}
private int atMost(int[] nums, int k) {
int len = nums.length;
int[] freq = new int[len + 1];
int left = 0;
int right = 0;
// [left, right) 里不同整数的个数
int count = 0;
int res = 0;
// [left, right) 包含不同整数的个数小于等于 K
while (right < len) {
if (freq[nums[right]] == 0) {
count++;
}
freq[nums[right]]++;
right++;
while (count > k) {
if (freq[nums[left]] == 1) {
count--;
}
freq[nums[left]]--;
left++;
}
// [left, right) 区间的长度就是对结果的贡献
res += right - left;
}
return res;
最长湍流子数组
给定一个整数数组arr ，返回arr的最大湍流子数组的长度 。
如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是 湍流子数组 。
更正式地来说，当 arr 的子数组 A[i], A[i+1], ..., A[j] 满足仅满足下列条件时，我们称其为湍流子数组：
若 i <= k < j ：
当 k 为奇数时， A[k] > A[k+1]，且
当 k 为偶数时，A[k] < A[k+1]；
或 若 i <= k < j ：
当 k 为偶数时，A[k] > A[k+1] ，且
当 k 为奇数时， A[k] < A[k+1]。
示例 1：
输入：arr = [9,4,2,10,7,8,8,1,9]
输出：5
解释：arr[1] > arr[2] < arr[3] > arr[4] < arr[5]
示例 2：
输入：arr = [4,8,12,16]
输出：2
示例 3：
输入：arr = [100]
输出：1
动态规划：波浪段， 这里不能只定义一个状态数组，
up[i] = i 结尾的， arr[i - 1] < arr[i] 的最长子数组长度
down[i] = i 结尾的， arr[i - 1] > arr[i] 的最长子数组长度
up[i] = down[i - 1] + 1
down[i] = up[i - 1] + 1
. i
arr: 9 4 2 10 7 8 8 1 9
up: 1 1 1 1 1 1 1 1 1
down: 1 1 1 1 1 1 1 1 1
. i
arr: 9 4 2 10 7 8 8 1 9
up: 1 1 1 1 1 1 1 1 1
down: 1 2 1 1 1 1 1 1 1
. i
arr: 9 4 2 10 7 8 8 1 9
up: 1 1 1 1 1 1 1 1 1
down: 1 2 2 1 1 1 1 1 1 down[i] = up[i - 1] + 1
. i i i i i i
arr: 9 4 2 10 7 8 8 1 9
up: 1 1 1 3 1 5 1 1 3
down: 1 2 2 1 4 1 1 2 1 up[i] = down[i - 1] + 1
public int maxTurbulenceSize(int[] arr) {
int res = 1, up = 1, down = 1;
for (int i = 1; i < arr.length; i++) {
if (arr[i - 1] < arr[i]) {
up = down + 1;
down = 1;
} else if (arr[i - 1] > arr[i]) {
down = up + 1;
up = 1;
} else {
up = 1;
down = 1;
}
res = Math.max(res, Math.max(up, down));
}
return res;
滑动窗口： 移动右指针：
[left, right + 1]
- arr[right - 1] < arr[right] && arr[right] > arr[right + 1]
- arr[right - 1] > arr[right] && arr[right] < arr[right + 1]
滑动窗口： 移动左指针：
[left, right + 1]
- 右窗口 2 个条件不满足时，左窗口 直接跳到右窗口
public int maxTurbulenceSize(int[] arr) {
int len = arr.length;
if (len < 2) {
return len;
}
int left = 0, right = 1;
// arr[i - 1] < arr[i] is true
boolean pre = false;
int res = 1;
while (right < len) {
boolean current = arr[right - 1] < arr[right];
if (current == pre) {
left = right - 1;
}
if (arr[right - 1] == arr[right]) {
left = right;
}
right++;
res = Math.max(res, right - left);
pre = current;
}
return res;
}
最大连续 1 的个数 III
给定一个二进制数组nums和一个整数k ，如果可以翻转最多k个0 ，则返回 数组中连续1的最大个数 。
示例 1：
输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。
示例 2：
输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。
窗口的常见做法，是 0 的时候 K - 1， 当 k 没了左边窗口就移动
class Sulution{
puclic int longestOnes(int[] nums, int k) {
int res = 0;
int count = 0;
for (int fast = 0, slow = 0; fast < nums.length; fast++) {
if (nums[fast] == 0) {
count++;
}
while (count > k) {
if (nums[slow++] == 0) {
count--;
}
}
res = Math.max(res, fast - slow + 1);
}
return res;
}
}
Replace the Substring for Balanced String
这道题我以为统计一下字符的频率就行了，发现不行，没想到是子序列，不能是任意位置。用双指针法，i 指向子串的左端，j 指向字符串的右端，当 i~j 去掉的字符串区间。维护 i 到 j 这个最小区间就行了。
You are given a string s of length n containing only four kinds of characters: 'Q', 'W', 'E', and 'R'.
A string is said to be balanced if each of its characters appears n / 4 times where n is the length of the string.
Return the minimum length of the substring that can be replaced with any other string of the same length to make s balanced. If s is already balanced, return 0.
Example 1:
Input: s = "QWER"
Output: 0
Explanation: s is already balanced.
Example 2:
Input: s = "QQWE"
Output: 1
Explanation: We need to replace a 'Q' to 'R', so that "RQWE" (or "QRWE") is balanced.
Example 3:
Input: s = "QQQW"
Output: 2
Explanation: We can replace the first "QQ" to "ER".
思路
注意要替换的是子串，必须连续，自然想到连续窗口
对于窗口内的可以任意替换，而窗口外的不能更改，所以这必然要求窗口外的各字母数量小于等于 n/4，这样才能在窗口内补上，但如果超过就不能更改，必然不满足条件，所以第一步先统计每个字母次数，用哈希表计数，（数组也可以）。 当窗口外计数满足，则更新答案，并试探更小的窗口；当不能缩小时再后移窗口。 对于每个窗口内的位置，将其计数减一，出窗口后就加一恢复，可变滑动窗口遍历整个字符串，最小窗口即是答案。
class Sulution{
puclic int longestOnes(int[] nums, int k) {
int[] count = new int[128];
int n = s.length(), res = n, i = 0, k = n / 4;
for (int j = 0; j < n; j++) {
count[s.charAt(j)]++;
}
for (int j = 0; j < n; j++) {
count[s.charAt(j)]--; // 窗口外的减少
while (i < n && count['Q'] <= k && count['W'] <= k && count['E'] <= k && count['R'] <= k) {
res = Math.min(res, j - i + 1);
count[s.charAt(i++)]++;
}
}
return res;
}
}
统计优美子数组
给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
请返回这个数组中 「优美子数组」 的数目。
示例 1：
输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
示例 2：
输入：nums = [2,4,6], k = 1
输出：0
解释：数列中不包含任何奇数，所以不存在优美子数组。
示例 3：
输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出：16
这道题其实求得是窗口外得值
2 3 4 2 5 6 2 k = 2
窗口：
2 [3 4 2 5] 6 2 k = 2
窗口前面有 2 个 * 窗口后面有 3 个 共 6 个子集
class Sulution{
int count = 0, res = 0;
int left = 0, right = 0;
while (right < nums.length) {
if (nums[right++] % 2 == 1) {
// 右指针先走，每遇到一个奇数则
count++;
}
// 若当前滑动窗口 [left, right) 中有 k 个奇数了，进入此分支统计当前滑动窗口中的优美子数组个数。
if (count == k) {
// 有窗口移动到下一个奇数后者边界
int tmp = right;
while(right < nums.length && nums[right] % 2 == 0) {
right++;
}
int rightB = right - tmp;
// leftEvenCnt 即为第 1 个奇数左边的偶数的个数
int leftB = 0;
while (nums[left] % 2 == 0) {
leftB++;
left++;
}
// 第 1 个奇数左边的 leftEvenCnt 个偶数都可以作为优美子数组的起点
// (因为第1个奇数左边可以1个偶数都不取，所以起点的选择有 leftEvenCnt + 1 种）
// 第 k 个奇数右边的 rightEvenCnt 个偶数都可以作为优美子数组的终点
// (因为第k个奇数右边可以1个偶数都不取，所以终点的选择有 rightEvenCnt + 1 种）
// 所以该滑动窗口中，优美子数组左右起点的选择组合数为 (leftEvenCnt + 1) * (rightEvenCnt + 1)
res += (leftB + 1) * (rightB + 1);
left++;
count--;
}
}
return res;
}
}
前缀和
计算前缀和数组 arr：遍历原数组，每遍历一个元素，计算当前的前缀和（即到当前元素为止，数组中有多少个奇数）； 对上述前缀和数组，双重循环统计 arr[j] - arr[i] == k 的个数，这样做是 O(N^2)O(N 2 ) 的（这里会超时哦）。
优化：因此，我们可以像「1. 两数之和」那样使用 HashMap 优化到 O(N)O(N)，键是「前缀和」，值是「前缀和的个数」（下面代码中具体使用的是 int[] prefixCnt 数组，下标是「前缀和」，值是「前缀和的个数」），因此我们可以遍历原数组，每遍历到一个元素，计算当前的前缀和 sum，就在 res 中累加上前缀和为 sum - k 的个数。 👇代码注释很详细👇（时间复杂度 O(N)O(N)，空间复杂度 O(N)O(N)）
class Solution {
public int numberOfSubarrays(int[] nums, int k) {
// 数组 prefixCnt 的下标是前缀和（即当前奇数的个数），值是前缀和的个数。
int[] prefixCnt = new int[nums.length + 1];
prefixCnt[0] = 1;
// 遍历原数组，计算当前的前缀和，统计到 prefixCnt 数组中，
// 并且在 res 中累加上与当前前缀和差值为 k 的前缀和的个数。
int res = 0, sum = 0;
for (int num: nums) {
sum += num & 1;
prefixCnt[sum]++;
if (sum >= k) {
res += prefixCnt[sum - k];
}
}
return res;
}
}
将 x 减到 0 的最小操作数
给你一个整数数组nums 和一个整数x 。每一次操作时，你应当移除数组nums 最左边或最右边的元素，然后从x中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。
示例 1：
输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
示例 2：
输入：nums = [5,6,7,8,9], x = 4
输出：-1
示例 3：
输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。
找外部最小即找中间最大
class Sulution{
public int minOperations(int[] nums, int x) {
// 滑动槽口找中间最早片段 sum -x
int max = -1;
int sum = Arrays.stream(nums).sum();
int target = sum - x;
int cur = 0;
int left = 0, right = 0;
while (right < nums.length) {
cur += nums[right];
while (cur > target) {
cur -= nums[left];
left++;
}
if (cur == count) {
max = Math.max(max, right - left + 1);
}
right++;
}
}
return max == -1 ? -1 : nums.length - max;
}
}
public int minOperations(int[] nums, int x) {
int sum= 0;
for(int num: nums) sum += num;
int target = sum -x;
if(target < 0) return -1; //因为数据全是正数
int left =0, right=0 ,max=Integer.MIN_VALUE;
while (right < nums.length){
target -=nums[right++];//窗口右侧主动扩张
while (target < 0) target+=nums[left++]; //窗口左侧适应性收缩
if(target==0) max=Math.max( max , right -left);//right以及
}
return max==Integer.MIN_VALUE? -1 :nums.length -max;
}
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/MPnaiL
感谢：她们都有题库在 github 上直接有，都是大神
