解題說明
題目描述
給定一個只包含 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 各佔一半）。
C++ 解法
複雜度分析
時間複雜度
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²)。
- 優點：無需轉換技巧，邏輯直觀。
- 缺點：時間 O(n²)，n 為 5×10^4 時（本題限制）約需 2.5×10^9 次操作，明顯超時。
方案二：滑動窗口（不適用）
本題子陣列長度不單調對應某個條件（0/1 計數差可增可減），滑動窗口無法維護有效的收縮條件，不適合本題。
方案三：排序前綴和（理論可行但非最優）
預計算所有前綴和（值為 -1 版本），然後排序，找最遠的同值前綴和對。
- 優點：思路與 HashMap 解法等價，適合理解「相同前綴和之間的子陣列」。
- 缺點：排序時間 O(n log n)，且需要在排序後追蹤原始索引，程式碼更複雜；HashMap 解法 O(n) 更優。
延伸思考
延伸問題
-
推廣到 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 存最早索引」的模式，是同一類問題的不同變體。