給定一個只包含 0 和 1 的二進位陣列 nums,找出最長的連續子陣列,使得子陣列中 0 和 1 的個數相等,回傳該子陣列的長度。
範例:nums = [0, 1, 0, 1, 1, 0, 0]
核心技巧:將 0 替換為 -1,問題轉化為求最長和為 0 的子陣列。
為什麼?若子陣列中 0 和 1 的個數相等,用 -1 替換 0 後,+1(來自 1)和 -1(來自 0)相消,和恰好為 0。
定義前綴和 sum[i](把 0 視為 -1 後)。若 sum[j] == sum[i](j > i),則子陣列 nums[i+1..j] 的和為 0,即 0 和 1 個數相等。
演算法:
[j+1, i] 的長度為 i - j,更新最大長度。初始化:HashMap 預先放入 {0: -1},處理從索引 0 開始整段前綴和為 0 的情況(即前 i+1 個元素中 0 和 1 各佔一半)。
O(n),其中 n 為陣列長度。只需一次線性遍歷,每次 HashMap 操作均為 O(1) 平均時間。
O(n),HashMap 最多儲存 n+1 個不同的前綴和值(範圍從 -n 到 +n,但實際出現的不超過 n+1 個)。
1. Initialize HashMap firstSeen = {0: -1}
2. Initialize sum = 0, maxLen = 0
3. For i from 0 to n-1:
a. If nums[i] == 1: sum += 1
Else: sum -= 1 (treat 0 as -1)
b. If firstSeen contains sum:
- maxLen = max(maxLen, i - firstSeen[sum])
- (Do NOT update firstSeen[sum])
c. Else: firstSeen[sum] = i
4. Return maxLen雙重迴圈枚舉所有子陣列,分別計算 0 和 1 的個數並比較。可用前綴和加速計算,但整體仍為 O(n²)。
本題子陣列長度不單調對應某個條件(0/1 計數差可增可減),滑動窗口無法維護有效的收縮條件,不適合本題。
預計算所有前綴和(值為 -1 版本),然後排序,找最遠的同值前綴和對。
推廣到 k 個類別:若陣列包含 0, 1, 2 三種值,如何找最長子陣列使三種值的個數相等?可以轉化為「(count_1 - count_0, count_1 - count_2)」這個二維前綴向量對,用 HashMap 找相同向量的最遠配對。一般化後可處理 k 種值,但狀態空間會指數增長。
計算滿足條件的子陣列數:若要計算所有「0 和 1 個數相等」的子陣列的個數(而非找最長),改用 count[sum] 記錄每個前綴和出現的次數,每次遇到相同前綴和時加上之前的 count 值,時間仍為 O(n)。
與 LC 523 的關係:本題(前綴和為 0)是 LC 523(前綴和為 k 的倍數)的特殊情況(k 無限大,或視作「和被 k 整除」k=任意)。兩者都用「前綴和 + HashMap 存最早索引」的模式,是同一類問題的不同變體。