How do I know if partitioning is possible in the "Partition Array Into Three Parts With Equal Sum" problem?

If the total sum of the array is not divisible by 3, partitioning is not possible. Otherwise, use a greedy approach to try and partition the array into three equal sums.

What are the key steps in solving "Partition Array Into Three Parts With Equal Sum"?

The steps include calculating the total sum, checking for divisibility by 3, then using a greedy approach to find the first two partitions while validating the third.

Can this problem be solved in less than linear time?

No, this problem generally requires linear time complexity, O(n), to scan through the array and validate possible partitions.

What is a common mistake when solving this problem?

A common mistake is not checking if the total sum is divisible by 3 before proceeding with the partitioning logic.

What variations can be made to the "Partition Array Into Three Parts With Equal Sum" problem?

Variations include increasing the number of partitions, requiring contiguous segments, or adding new constraints like negative numbers.

#1013

Easy

auto_awesome贪心·invariant

LeetCode 题解工作台

将数组分成和相等的三个部分

给你一个整数数组 arr ，只有可以将其划分为三个和相等的非空部分时才返回 true ，否则返回 false 。形式上，如果可以找出索引 i + 1 且满足 (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + a…

数组贪心

题目描述

给你一个整数数组 arr，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。

形式上，如果可以找出索引 i + 1 < j 且满足 (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1]) 就可以将数组三等分。

示例 1：

输入：arr = [0,2,1,-6,6,-7,9,1,2,0,1]
输出：true
解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

示例 2：

输入：arr = [0,2,1,-6,6,7,9,-1,2,0,1]
输出：false

示例 3：

输入：arr = [3,3,6,5,-2,2,5,1,-9,4]
输出：true
解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

提示：

3 <= arr.length <= 5 * 10⁴
-10⁴ <= arr[i] <= 10⁴

lightbulb

解题思路

方法一：遍历求和

我们先求出整个数组的和，然后判断和是否能被 3 整除，如果不能，直接返回 $\textit{false}$ 。

否则，我们记 $\textit{s}$ 表示每部分的和，用一个变量 $\textit{cnt}$ 记录当前已经找到的部分数，另一个变量 $\textit{t}$ 记录当前部分的和。初始时 $\textit{cnt} = 0$ , $t = 0$ 。

然后我们遍历数组，对于每个元素 $x$ ，我们将 $t$ 加上 $x$ ，如果 $t$ 等于 $s$ ，说明找到了一部分，将 $\textit{cnt}$ 加一，然后将 $t$ 置为 0。

最后判断 $\textit{cnt}$ 是否大于等于 3 即可。

时间复杂度 $O(n)$ ，其中 $n$ 是数组 $\textit{arr}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def canThreePartsEqualSum(self, arr: List[int]) -> bool:
        s, mod = divmod(sum(arr), 3)
        if mod:
            return False
        cnt = t = 0
        for x in arr:
            t += x
            if t == s:
                cnt += 1
                t = 0
        return cnt >= 3

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Test candidate's understanding of greedy techniques and how it applies to partitioning problems.
question_mark
Check if the candidate can efficiently handle large input arrays with O(n) complexity.
question_mark
Look for the ability to break down the problem into smaller, logical steps with careful validation of invariants.

warning

常见陷阱

外企场景

error
Failing to check if the total sum of the array is divisible by 3, which is an early termination condition.
error
Rushing the partitioning step without checking that the sums are being validated after each greedy choice.
error
Ignoring edge cases where the array length is too small or the elements are too varied to form three equal partitions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to ask for splitting the array into four or more parts with equal sums.
arrow_right_alt
Change the array constraints to allow negative numbers only and test the handling of those scenarios.
arrow_right_alt
Introduce an additional constraint that the partitions must be contiguous, not just non-empty, and evaluate the solution approach.

help

常见问题

外企场景

继续练习

#1007 行相等的最少多米诺旋转 #1005 K 次取反后最大化的数组和 #1024 视频拼接