算法專區 解構線性掃描序列的必勝法 (固定長度與可變長度)

概念

「移動視窗」是一種線性掃描序列的方法, 常用在子陣列 / 子字串 / 子序列 問題上

常見兩種滑動視窗

1. 固定長度窗口 : 已知子陣列長度, 例如找長度為 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

2. 可變長度窗口 (雙指針) : 像「最小長度子陣列和 >= 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 的累加或更新
• 可變長度 -> 常用 「條件滿足就縮左邊, 不滿就擴右邊」