下面為模板代碼，還會(huì)附上一道例題
int left = 0, right = 0;
while (right < s.size()) {
// 增大窗口
window.add(s[right]);
right++;
while (window needs shrink) {
// 縮小窗口
window.remove(s[left]);
left++;
}
}
在處理數(shù)組（或LinkedList）的許多問(wèn)題中痕貌，要求我們?cè)诮o定大小的所有連續(xù)子數(shù)組（或子列表）中查找或計(jì)算某些東西邪意。 例如隙赁，看一下這個(gè)問(wèn)題：
給定一個(gè)數(shù)組经宏，求其中所有大小為K的連續(xù)子數(shù)組的平均值
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:
- 先說(shuō)一下result數(shù)組的大小怎么確定的良蛮，示例中給你9個(gè)元素哪怔，減去5個(gè)等于4個(gè)灶伊，也就是說(shuō)弥鹦，假如你把最后五個(gè)捆一起肚逸，可以往前移動(dòng)四個(gè)次，每次一個(gè)單位彬坏，即有四個(gè)可移動(dòng)空間朦促，再算上他沒(méi)有移動(dòng)之前，也占一個(gè)單位栓始，所以4+1=5
- 注意到(windowEnd-1) - windowStart + 1 == K务冕，這里windowEnd-1，是因?yàn)槲姨崆皩indowEnd指針后移幻赚，指向下一個(gè)元素禀忆，而判斷條件時(shí)，是對(duì)窗口內(nèi)的元素進(jìn)行判斷落恼，此時(shí)windowEnd在窗口的外面箩退，所以減去1，而且要記住兩個(gè)索引相減再加一佳谦，就是區(qū)間內(nèi)元素的個(gè)數(shù)
