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

标签: 贪心 数组

难度: Easy

给你一个整数数组 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 * 104
  • -104 <= arr[i] <= 104

Submission

运行时间: 27 ms

内存: 21.9 MB

class Solution:
    def canThreePartsEqualSum(self, arr: List[int]) -> bool:
        total = sum(arr)
        each_sum = total // 3
        if total % 3 != 0: return False
        sumi = count = 0
        for x in arr:
            sumi += x
            if sumi == each_sum:
                sumi = 0
                count += 1
                if count == 3: return True
        return False

Explain

首先计算数组 arr 的总和 total。如果 total 不是 3 的倍数，则直接返回 False，因为不能平均分成三个相同的部分。如果 total 是 3 的倍数，则定义 each_sum 为 total 除以 3 的结果。接下来，遍历数组 arr，累加元素值到临时变量 sumi。每当 sumi 等于 each_sum 时，将 sumi 重置为 0，并将 count（记录达到 each_sum 的次数）加 1。如果 count 达到 3 次，即在数组结束前已找到三个部分和为 each_sum，则返回 True。如果遍历完成后，没有找到三个这样的部分，则返回 False。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def canThreePartsEqualSum(self, arr: List[int]) -> bool:
        total = sum(arr)  # 计算整个数组的总和
        each_sum = total // 3  # 计算每部分应有的和
        if total % 3 != 0: return False  # 如果总和不是3的倍数，直接返回False
        sumi = count = 0  # 初始化当前部分的和为0和找到的部分数量为0
        for x in arr:
            sumi += x  # 累加当前元素到部分和中
            if sumi == each_sum:  # 如果当前部分的和达到了目标和
                sumi = 0  # 重置部分和为0
                count += 1  # 增加找到的部分数量
                if count == 3: return True  # 如果已经找到三个部分，则返回True
        return False  # 如果结束后没有找到三个符合条件的部分，则返回False

Explore

当算法在遍历过程中第三次达到`each_sum`时，意味着已经成功划分出三个和为`each_sum`的部分。此时，算法直接返回True是基于这样的逻辑：前两部分和第三部分的总和等于整个数组的总和，即3倍的`each_sum`。由于总和已经被验证为3的倍数，找到了三个这样的部分就意味着其余的元素和也必然是`each_sum`。因此，不需要额外验证第三部分是否延续到数组的末尾，它自然满足条件。

在`sumi`达到`each_sum`后将`sumi`重置为0是为了重新开始计算下一个部分的和，这确保了每个部分都是从前一个部分结束的地方连续开始的。由于累加是连续的，每次重置`sumi`都意味着开始新的连续子数组。这种方法确保了每个部分不仅和为`each_sum`，而且是数组中连续的片段。

数组中存在的负数或零不会影响算法的正确性。算法的目标是找到三个和为`each_sum`的连续部分，不论这些部分中的元素是正数、负数还是零。只要这些部分的和达到了预定的`each_sum`，无论组成元素的具体值如何，都满足题目要求。因此，包含负数或零的数组同样适用于此算法。

如果`count`在数组未完全遍历前就达到3，这实际上不会导致误判。这是因为算法确保了每次`count`增加时，已找到的部分和必然是`each_sum`。一旦`count`达到3，意味着我们已经找到了三个部分的总和等于3倍的`each_sum`，即数组的总和。此时，即使数组没有遍历完，剩余部分的总和必然为0，这不会影响已经找到的三个部分满足题目条件。