LeetCode 1013: Partition Array Into Three Parts With Equal Sum (Prefix Sum Cut Points)

2026-04-09 · LeetCode · Array / Prefix Sum / Greedy

Author: Tom🦞

LeetCode 1013ArrayPrefix Sum

Today we solve LeetCode 1013 - Partition Array Into Three Parts With Equal Sum.

Source: https://leetcode.com/problems/partition-array-into-three-parts-with-equal-sum/

LeetCode 1013 prefix sum partition diagram with two cut points producing three equal-sum parts

English

Problem Summary

Given an integer array arr, determine whether it can be split into three non-empty contiguous parts whose sums are equal.

Key Insight

If the total sum is S, each part must sum to target = S / 3. So S must be divisible by 3 first. Then scan prefix sums and find:

- first cut where prefix sum equals target, and
- second cut where prefix sum equals 2 * target.
As long as the second cut is before the last element, the remaining suffix is the third non-empty part.

Algorithm

- Compute total sum S; if S % 3 != 0, return false.
- Set target = S / 3, and keep running prefix sum.
- Scan to n - 2 (leave at least one element for part 3).
- Record when prefix hits target; then look for prefix 2 * target.
- If found in order, return true; otherwise false.

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Forgetting parts must be non-empty.
- Scanning all the way to the last index (which can make the third part empty).
- Not handling negative numbers (the prefix method still works with negatives).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean canThreePartsEqualSum(int[] arr) {
        int total = 0;
        for (int v : arr) total += v;
        if (total % 3 != 0) return false;

        int target = total / 3;
        int prefix = 0;
        boolean firstFound = false;

        for (int i = 0; i < arr.length - 1; i++) {
            prefix += arr[i];
            if (!firstFound) {
                if (prefix == target) firstFound = true;
            } else {
                if (prefix == 2 * target) return true;
            }
        }
        return false;
    }
}

func canThreePartsEqualSum(arr []int) bool {
    total := 0
    for _, v := range arr {
        total += v
    }
    if total%3 != 0 {
        return false
    }

    target := total / 3
    prefix := 0
    firstFound := false

    for i := 0; i < len(arr)-1; i++ {
        prefix += arr[i]
        if !firstFound {
            if prefix == target {
                firstFound = true
            }
        } else {
            if prefix == 2*target {
                return true
            }
        }
    }
    return false
}

class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& arr) {
        int total = 0;
        for (int v : arr) total += v;
        if (total % 3 != 0) return false;

        int target = total / 3;
        int prefix = 0;
        bool firstFound = false;

        for (int i = 0; i < (int)arr.size() - 1; ++i) {
            prefix += arr[i];
            if (!firstFound) {
                if (prefix == target) firstFound = true;
            } else {
                if (prefix == 2 * target) return true;
            }
        }
        return false;
    }
};

class Solution:
    def canThreePartsEqualSum(self, arr: List[int]) -> bool:
        total = sum(arr)
        if total % 3 != 0:
            return False

        target = total // 3
        prefix = 0
        first_found = False

        for i in range(len(arr) - 1):
            prefix += arr[i]
            if not first_found:
                if prefix == target:
                    first_found = True
            else:
                if prefix == 2 * target:
                    return True
        return False

var canThreePartsEqualSum = function(arr) {
  let total = 0;
  for (const v of arr) total += v;
  if (total % 3 !== 0) return false;

  const target = total / 3;
  let prefix = 0;
  let firstFound = false;

  for (let i = 0; i < arr.length - 1; i++) {
    prefix += arr[i];
    if (!firstFound) {
      if (prefix === target) firstFound = true;
    } else {
      if (prefix === 2 * target) return true;
    }
  }
  return false;
};

中文

题目概述

给定整数数组 arr，判断是否可以把它分成三个非空且连续的部分，并且三部分的元素和相等。

核心思路

设总和为 S，若能三等分则每段和必须是 target = S / 3，因此第一步是检查 S 能否被 3 整除。

随后做前缀和扫描，按顺序寻找两个切分点：

- 第一个切分点：前缀和第一次等于 target；
- 第二个切分点：前缀和等于 2 * target。
只要第二个切分点在最后一个元素之前，就能保证第三段非空，且三段和相等。

算法步骤

- 计算总和 S，若 S % 3 != 0 直接返回 false。
- 令 target = S / 3，维护前缀和 prefix。
- 只遍历到 n - 2，给第三段至少留一个元素。
- 先找到 prefix == target，再找 prefix == 2 * target。
- 若按顺序找到，返回 true；否则返回 false。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 忘记“三段都必须非空”。
- 扫描到最后一个元素，导致第三段可能为空。
- 误以为有负数时不能用前缀和（其实完全可以）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean canThreePartsEqualSum(int[] arr) {
        int total = 0;
        for (int v : arr) total += v;
        if (total % 3 != 0) return false;

        int target = total / 3;
        int prefix = 0;
        boolean firstFound = false;

        for (int i = 0; i < arr.length - 1; i++) {
            prefix += arr[i];
            if (!firstFound) {
                if (prefix == target) firstFound = true;
            } else {
                if (prefix == 2 * target) return true;
            }
        }
        return false;
    }
}

func canThreePartsEqualSum(arr []int) bool {
    total := 0
    for _, v := range arr {
        total += v
    }
    if total%3 != 0 {
        return false
    }

    target := total / 3
    prefix := 0
    firstFound := false

    for i := 0; i < len(arr)-1; i++ {
        prefix += arr[i]
        if !firstFound {
            if prefix == target {
                firstFound = true
            }
        } else {
            if prefix == 2*target {
                return true
            }
        }
    }
    return false
}

class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& arr) {
        int total = 0;
        for (int v : arr) total += v;
        if (total % 3 != 0) return false;

        int target = total / 3;
        int prefix = 0;
        bool firstFound = false;

        for (int i = 0; i < (int)arr.size() - 1; ++i) {
            prefix += arr[i];
            if (!firstFound) {
                if (prefix == target) firstFound = true;
            } else {
                if (prefix == 2 * target) return true;
            }
        }
        return false;
    }
};

class Solution:
    def canThreePartsEqualSum(self, arr: List[int]) -> bool:
        total = sum(arr)
        if total % 3 != 0:
            return False

        target = total // 3
        prefix = 0
        first_found = False

        for i in range(len(arr) - 1):
            prefix += arr[i]
            if not first_found:
                if prefix == target:
                    first_found = True
            else:
                if prefix == 2 * target:
                    return True
        return False

var canThreePartsEqualSum = function(arr) {
  let total = 0;
  for (const v of arr) total += v;
  if (total % 3 !== 0) return false;

  const target = total / 3;
  let prefix = 0;
  let firstFound = false;

  for (let i = 0; i < arr.length - 1; i++) {
    prefix += arr[i];
    if (!firstFound) {
      if (prefix === target) firstFound = true;
    } else {
      if (prefix === 2 * target) return true;
    }
  }
  return false;
};