LeetCode 927: Three Equal Parts ·

基本資料
#

難易度: hard 第一次嘗試：2025-07-16

提交紀錄：18 次（WA / RE 很多次 → 2025-07-17 早上 AC → 重寫又錯 7 次 → AC）

解題思路
#

前導零不影響值，所以三段代表同一個二進位數 ⇔ 去掉前導零之後完全一樣。

三段的 1 一定一樣多：總數不能被 3 整除就不可能。
全部都是 0：任何切法都是 0，回傳 [0, n - 1]。
每段有 k = 1 的總數 / 3 個 1。找出第 1、k + 1、2k + 1 個 1 的位置 a、b、c，它們分別是三段去掉前導零後的開頭。
第三段一定延伸到陣列尾端，尾端的 0 都算它的，所以每段的長度（從第一個 1 算起）都是 L = n - c。
檢查 arr[a:a+L]、arr[b:b+L]、arr[c:] 是否一樣，而且第一段結束在第二段開始之前（a + L <= b）、第二段結束在第三段開始之前（b + L <= c）。
答案是 [a + L - 1, b + L]。

我的嘗試
#

這題我寫了 18 次。前 9 次是從右往左掃、邊掃邊用 2 ** (位置) 累加每段的值，邊界一直出問題：

全部是 0 時沒處理：[0, 0, 0] 會直接 IndexError（res 是空的），或回傳 [-1, -1]，答案是 [0, 2]。中間有一版甚至寫成 if arr == [0, 0, 0, 0, 0]: return [0, 4] 來過特定測資。
第一次 AC 是把它改成 part_count == 0 時回傳 [0, n - 1]。

同一天早上又用「先取出第三段的樣板，再往左比對」重寫了一次，回傳的 index 加不加 1、樣板的位置一直弄錯，又錯了 7 次。例如 [1, 1, 1] 回傳了 [0, 1]（答案是 [0, 2]），[1, 1, 1, 1, 1, 1] 回傳 [1, 3]（答案是 [1, 4]）。

上面的解法用三個位置 a、b、c 直接比對，不需要算值，也比較不會差一。

正確解法
#

class Solution:
    def threeEqualParts(self, arr: List[int]) -> List[int]:
        n = len(arr)
        ones = sum(arr)
        if ones == 0:
            return [0, n - 1]                      # 全部是 0
        if ones % 3:
            return [-1, -1]
        k = ones // 3

        starts = []                                # 第 1、k+1、2k+1 個 1 的位置
        seen = 0
        for i, x in enumerate(arr):
            if x:
                if seen % k == 0:
                    starts.append(i)
                seen += 1
        a, b, c = starts
        L = n - c                                  # 第三段延伸到尾端，決定長度

        if a + L <= b and b + L <= c and arr[a:a + L] == arr[b:b + L] == arr[c:]:
            return [a + L - 1, b + L]
        return [-1, -1]