Chia Mảng Thành 3 Phần Tổng Bằng Nhau (Partition Array Into Three Parts) Trong Python

Cho mảng A. Kiểm tra có thể chia thành 3 phần liên tiếp, không rỗng có tổng bằng nhau hay không. Tức tìm i+1 < j sao cho:

sum(A[0..i]) == sum(A[i+1..j-1]) == sum(A[j..n-1])

Ví dụ: [0,2,1,-6,6,-7,9,1,2,0,1] → True (3 phần: [0,2,1], [-6,6,-7,9,1], [2,0,1] đều tổng = 3).

Thuật toán tối ưu O(n)

1. Tổng toàn mảng total = sum(A). Nếu total % 3 != 0 → False
2. target = total // 3
3. Duyệt trái sang phải, tính tổng tiền tố cur_sum:
   • Khi cur_sum == target: tìm được phần 1, reset cur_sum = 0, tăng đếm phần
4. Cần tìm được 2 phần (phần 3 tự động đúng vì tổng chia hết 3)
5. Đảm bảo phần 3 không rỗng: chỉ đếm phần 1,2 khi chưa đến cuối mảng

Ví dụ (Python)

class Solution(object):
    def canThreePartsEqualSum(self, A):
        total = sum(A)
        if total % 3 != 0:
            return False
        
        target = total // 3
        cur_sum = 0
        parts_found = 0
        
        for i in range(len(A) - 1):  # -1 để phần 3 không rỗng
            cur_sum += A[i]
            if cur_sum == target:
                parts_found += 1
                cur_sum = 0
                if parts_found == 2:
                    return True
        
        return False

ob1 = Solution()
print(ob1.canThreePartsEqualSum([0,2,1,-6,6,-7,9,1,2,0,1]))  # True
print(ob1.canThreePartsEqualSum([0,2,1,-6,6,7,9,-1,2,0,1]))  # False
print(ob1.canThreePartsEqualSum([3,3,6,5,-2,2,5,1,-9,4]))    # True

Độ phức tạp

• Thời gian: O(n) - duyệt 1 lần
• Không gian: O(1)

Đầu vào / Đầu ra

Input:  [0,2,1,-6,6,-7,9,1,2,0,1]
Output: True