定长滑动窗口
# 定长滑动窗口
定长滑动窗口，是窗口长度固定，依次滑动。
# 图示
# 模板
定长类滑动窗口，例如窗口长度为k，第一步先移动k个元素，第二步再固定移动到结束，两步一般分开写。当然也可以写到一个循环体内，但是会加if判断，因此一般分开写，效率会更高点。
var fixedLength = function (nums, k) {
// 1. 先计算前k个元素
let window = 0;
for (let i = 0; i < k; i++) {
window += nums[i];
}
// 2. 移动窗口到数组结尾
let max = window;
for (let i = k; i < nums.length; i++) {
// 加入新元素，移除最左边元素，移动窗口
window = window + nums[i] - nums[i - k];
max = Math.max(max, window);
right++;
}
return max;
};
# 例题
# LC 643. 子数组最大平均数 I
Q：给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
A：这个问题是经典的定长滑动窗口入门题目。
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findMaxAverage = function (nums, k) {
// sliding window
let sum = 0;
let max = 0;
// 1. 计算前k个元素的和
for (let i = 0; i < k; i++) {
sum += nums[i];
}
// 2. 移动滑动窗口，记录最大的窗口之和
max = sum;
for (let i = k; i < nums.length; i++) {
sum = sum + nums[i] - nums[i - k];
max = Math.max(max, sum);
}
return max / k;
};
# LC 1423. 可获得的最大点数
Q：
几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。
A：这个题目也是定长类问题，特别点在于思维的转化。由于只能从开头或末尾拿，因此这里有两个解法：正向思维和反向思维
- 正向思维，滑动区间在 [n-k, n-1] - [0, k-1]，因此可以先移动k个元素，然后反向滑动，核心点处理好窗口左指针
- 逆向思维，当两边最大时，中间必然最小，因此问题可转化为求中间最小点数，则两边最大点数 = 总的点数 - 中间最小点数。该解法需要仔细体会，很多问题都在于转化，问题可能做了修饰，因此先根绝模式识别找到基础解法，然后对问题做层层转化。
/**
* @param {number[]} cardPoints
* @param {number} k
* @return {number}
*/
var maxScore = function (cardPoints, k) {
// 正向思维， [n-k, n-1] - [0, k-1]
{
// sliding window
let window = 0;
// 先移动k步
for (let i = 0; i < k; i++) {
window += cardPoints[i];
}
let max = window;
// 然后左移
let left = cardPoints.length - 1;
let right = k - 1;
while (right >= 0) {
window = window + cardPoints[left] - cardPoints[right];
max = Math.max(max, window);
left--;
right--;
}
return max;
}
// 逆向思维，两边最大 = 总点数 - 中间最小
{
// sliding window
// 逆向思维，求 n - k 个窗口内 和最小
const n = cardPoints.length;
let sum = 0;
let total = 0;
// 先移动k步
for (let i = 0; i < n - k; i++) {
sum += cardPoints[i];
}
total = sum;
// 求中间最小
let min = sum;
for (let i = n - k; i < n; i++) {
sum = sum + cardPoints[i] - cardPoints[i - (n - k)];
min = Math.min(min, sum);
total += cardPoints[i];
}
// 两边最大 = 总点数 - 中间最小
return total - min;
}
};
# 小结
定长类滑动窗口是基础形式，需要注意以下几点：
- 注意模板的写法，一般分两步，先移动k步，再移动到最后，避免循环体内判断语句
- 部分题目会对题目做修饰，对问题做掩盖，因此需要做好分析，对问题层层剖析，最后做转化。
定长类滑动窗口其实是不定长类的一个子集，但是由于其固定长度的特性，分为两步走，效率会更高。