927.md

927. Three Equal Parts

Solution 1 (time O(n), space O(1))

class Solution(object):
    def threeEqualParts(self, arr):
        """
        :type arr: List[int]
        :rtype: List[int]
        """
        sum_arr = sum(arr)
        if sum_arr == 0:
            return [0, 2]
        if sum_arr % 3 != 0:
            return [-1, -1]
        part_sum = sum_arr // 3
        p1 = p2 = p3 = cur_sum = 0
        for i, num in enumerate(arr):
            if num == 1:
                if cur_sum == 0:
                    p1 = i
                elif cur_sum == part_sum:
                    p2 = i
                elif cur_sum == 2 * part_sum:
                    p3 = i
                cur_sum += 1
        n = len(arr)
        part_length = n - p3
        if p1 + part_length <= p2 and p2 + part_length <= p3:
            p = 0
            while p3 + p < n:
                if arr[p1 + p] != arr[p2 + p] or arr[p1 + p] != arr[p3 + p]:
                    return [-1, -1]
                p += 1
            return [p1 + part_length - 1, p2 + part_length]
        return [-1, -1]