題目描述
給定一個只包含 0 和 1 的二進位陣列 nums,找出最長的連續子陣列,使得子陣列中 0 和 1 的個數相等,回傳該子陣列的長度。
範例:nums = [0, 1, 0, 1, 1, 0, 0]
- 子陣列 [0, 1, 0, 1, 1, 0, 0](整個陣列)中 0 有 4 個,1 有 3 個,不相等
- 子陣列 [0, 1, 0, 1] 中各有 2 個 → 長度 4
- 子陣列 [1, 0, 1, 1, 0, 0] 中各有 3 個 → 長度 6 ✓
解題思路
轉換問題:0 視為 -1
核心技巧:將 0 替換為 -1,問題轉化為求最長和為 0 的子陣列。
為什麼?若子陣列中 0 和 1 的個數相等,用 -1 替換 0 後,+1(來自 1)和 -1(來自 0)相消,和恰好為 0。
前綴和 + HashMap
定義前綴和 sum[i](把 0 視為 -1 後)。若 sum[j] == sum[i](j > i),則子陣列 nums[i+1..j] 的和為 0,即 0 和 1 個數相等。
演算法:
- HashMap 儲存每個前綴和第一次出現的索引。
- 遍歷陣列,維護當前前綴和。
- 若當前前綴和已在 HashMap 中出現(設索引為 j),則子陣列
[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 個)。
替代方案
方案一:暴力枚舉
雙重迴圈枚舉所有子陣列,分別計算 0 和 1 的個數並比較。可用前綴和加速計算,但整體仍為 O(n²)。
- 優點:無需轉換技巧,邏輯直觀。
- 缺點:時間 O(n²),n 為 5×10^4 時(本題限制)約需 2.5×10^9 次操作,明顯超時。
方案二:滑動窗口(不適用)
本題子陣列長度不單調對應某個條件(0/1 計數差可增可減),滑動窗口無法維護有效的收縮條件,不適合本題。
方案三:排序前綴和(理論可行但非最優)
預計算所有前綴和(值為 -1 版本),然後排序,找最遠的同值前綴和對。
- 優點:思路與 HashMap 解法等價,適合理解「相同前綴和之間的子陣列」。
- 缺點:排序時間 O(n log n),且需要在排序後追蹤原始索引,程式碼更複雜;HashMap 解法 O(n) 更優。