下面为模板代码，还会附上一道例题
int left = 0, right = 0;
while (right < s.size()) {
// 增大窗口
window.add(s[right]);
right++;
while (window needs shrink) {
// 缩小窗口
window.remove(s[left]);
left++;
}
}
在处理数组（或LinkedList）的许多问题中，要求我们在给定大小的所有连续子数组（或子列表）中查找或计算某些东西。 例如，看一下这个问题：
给定一个数组，求其中所有大小为K的连续子数组的平均值
Array: [1, 3, 2, 6, -1, 4, 1, 8, 2], K=5
答案为：[2.2, 2.8, 2.4, 3.6, 2.8]
public static double[] findAverages(int K, int[] arr) {
double[] result = new double[arr.length - K + 1];
double windowSum = 0;
int windowStart = 0, windowEnd = 0, index = 0;
while (windowEnd < arr.length) {
//增大窗口
windowSum += arr[windowEnd];
windowEnd++;
//判断window是否满足条件
while ((windowEnd-1) - windowStart + 1 == K) {
//更新答案
result[index++] = windowSum / K;
//缩小窗口
windowSum -= arr[windowStart];
windowStart++;
}
}
return result;
}
Tips:
- 先说一下result数组的大小怎么确定的，示例中给你9个元素，减去5个等于4个，也就是说，假如你把最后五个捆一起，可以往前移动四个次，每次一个单位，即有四个可移动空间，再算上他没有移动之前，也占一个单位，所以4+1=5
- 注意到(windowEnd-1) - windowStart + 1 == K，这里windowEnd-1，是因为我提前将windowEnd指针后移，指向下一个元素，而判断条件时，是对窗口内的元素进行判断，此时windowEnd在窗口的外面，所以减去1，而且要记住两个索引相减再加一，就是区间内元素的个数
