1013. Partition Array Into Three Parts With Equal Sum

題目描述

給定一個整數陣列 arr，判斷是否能將其分割為三個非空的連續子陣列，使得三個子陣列的元素總和相等。

即找到索引 i < j，使得：

• arr[0] + ... + arr[i] = arr[i+1] + ... + arr[j] = arr[j+1] + ... + arr[n-1]

解題思路

核心觀察

若陣列可以三等分，則每部分的總和必須等於 total / 3。因此：

1. 若 total % 3 != 0，直接回傳 false。
2. 否則，目標每份和為 target = total / 3。

貪心掃描

從左到右累積前綴和，每當前綴和達到 target 的整數倍時，就記錄一個分割點：

• 第一次累積到 target：記錄找到第一段，計數器 +1。
• 第二次累積到 2 * target：記錄找到第二段，計數器 +1。
• 關鍵：第三段不需要顯式檢查——只要前兩段找到了，且第二段的結束不是陣列末尾（確保第三段非空），第三段的和必然等於 total - 2*target = target。

邊界處理

• total = 0 的情況：若總和為 0，target 也為 0，任何前綴和都可能等於 0。需要確保找到兩個分割點，且第二個分割點不在最後一個元素（保證第三段非空）。
• 在迴圈結束條件上，第二個分割點必須在索引 n-2 或更早（即 i < n-1 時才能記錄第二個分割點），確保最後一段有元素。

實作時，用 parts 計數器追蹤已確認的段數。掃描到索引 i 時，若 parts < 2，才記錄分割（若 parts 已等於 2 不再更新，避免「最後一段為空」）。最終若 parts >= 2 即成功。

時間複雜度

O(n)，其中 n 為陣列長度。只需遍歷陣列兩次（一次計算總和，一次掃描分割點），每次皆為線性時間。

空間複雜度

O(1)，只使用了常數個額外變數（total、target、parts、running），不需要額外陣列。

替代方案

方案一：雙指標掃描

用左右兩個指標分別從陣列兩端向中間收縮，左側累積到 target 時移動左指標，右側累積到 target 時移動右指標，最後檢查中間剩餘部分是否也等於 target。

• 優點：同樣 O(n) 時間、O(1) 空間，且邏輯清晰直觀。
• 缺點：程式碼略長，需同時維護左右累積和，邊界條件稍微複雜。

方案二：前綴和陣列 + 二分搜尋

預先建立前綴和陣列，然後對每個可能的第一段終點用二分搜尋找第二段終點。

• 優點：邏輯直覺，前綴和陣列方便複用。
• 缺點：時間 O(n log n)、空間 O(n)，不如線性解法高效，屬於過度設計。

方案三：暴力枚舉分割點

枚舉所有可能的 (i, j) 分割點組合，計算三段的和並比較。

• 優點：思路最直接，無需前綴和知識。
• 缺點：時間複雜度 O(n²) 甚至 O(n³)（若不用前綴和），無法通過大資料量測試。

延伸問題

1. 分割為 k 等份：若要將陣列分為 k 個總和相等的非空連續子陣列，如何修改演算法？（需找到 k-1 個分割點，且每個分割點前的前綴和依次為 total/k, 2*total/k, ..., (k-1)*total/k。）

2. 子陣列不需連續：若允許每個子陣列包含任意選取的元素（不限連續），問題變為「能否將陣列分割為三個子集使總和相等」，這是 NP-hard 的子集和問題，需要動態規劃或回溯法。

3. 最大化最小段和：如果不要求三段和相等，而是要在所有合法的三段分割中，使「最小段的總和」最大化，應該怎麼做？（可用二分搜尋答案 + 貪心驗證，時間複雜度 O(n log(sum)) 。）