概念
「移動視窗」是一種線性掃描序列的方法, 常用在子陣列 / 子字串 / 子序列 問題上
常見兩種滑動視窗
- 固定長度窗口 : 已知子陣列長度, 例如找長度為 k 的子陣列最大和
流程 :
A. 用一個變數 window_sum 紀錄窗口內的總和
B. 先把前 k 個元素加入窗口
C. 窗口有右邊移動 : 移除左邊的元素, 加入新的右邊元素, 更新 window_sum 或其他資訊
int[] nums = {1, 2, 3, 4, 5};
int k = 3;
int maxSum = 0;
int windowSum = 0;
// 先計算前 k 個元素
for (int i = 0; i < k; i++) {
windowSum += nums[i];
}
maxSum = windowSum;
// 滑動窗口
for(int i = k; i < nums.length; i++) {
windowSum = windowSum - nums[i-k] + nums[i] // 左邊出去, 右邊進來
maxSum = Math.max(maxSum, windowSum);
}
System.out.println(maxSum) // 12
- 可變長度窗口 (雙指針) : 像「最小長度子陣列和 >= target」或 「不重複字符號的最長子字串」
技巧 : 用 left, right 兩個指針定義窗口範圍 [left, right], 根據條件決定, 擴大右邊縮小左邊
String s = "abcabcbb";
Set<Character> set = new HashSet<>();
int left = 0, right = 0, maxLen = 0;
while(right < s.length()) {
if (!set.contains(s.charAt(right)) {
set.add(s.cahrAt(right));
right++;
maxLen = Math.max(maxLen, set.size());
}else {
set.remove(s.charAt(left));
left++;
}
}
System.out.println(maxLen) // 3 ("abc")
總結
- 滑動視窗就是一個範圍在數列上移動, 避免每次都重新掃描整個子序列
- 固定長度 -> 常用 sum / max / min 的累加或更新
- 可變長度 -> 常用 「條件滿足就縮左邊, 不滿就擴右邊」
