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 * 10^4
  • -10^4 <= arr[i] <= 10^4

解题思路

解题思路

这道题的核心思想是：如果数组可以分成三个相等和的部分，那么每部分的和必须等于总和的三分之一。

主要思路：

  1. 预判断：首先计算数组的总和，如果总和不能被3整除，直接返回false
  2. 目标确定：计算每部分应有的和 target = sum / 3
  3. 双指针查找：使用前缀和的思想，找到第一个和第二个分割点
    • 从左往右找到第一个前缀和等于target的位置
    • 继续往右找到第二个前缀和等于2×target的位置
    • 如果两个位置都找到且满足索引关系，说明可以三等分

算法步骤：

  • 计算总和并检查是否能被3整除
  • 使用一次遍历，维护前缀和
  • 记录找到第一部分和第二部分的位置
  • 验证是否存在合法的分割方案

时间复杂度优化： 只需要一次遍历即可完成，无需多次扫描数组。

边界处理： 注意每个部分都必须非空，所以分割点的选择要保证三个部分都至少有一个元素。

代码实现

class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& arr) {
        int total = accumulate(arr.begin(), arr.end(), 0);
        if (total % 3 != 0) return false;
        
        int target = total / 3;
        int n = arr.size();
        int sum = 0;
        int firstPart = -1, secondPart = -1;
        
        for (int i = 0; i < n; i++) {
            sum += arr[i];
            if (sum == target && firstPart == -1) {
                firstPart = i;
            } else if (sum == 2 * target && firstPart != -1) {
                secondPart = i;
                break;
            }
        }
        
        return firstPart != -1 && secondPart != -1 && secondPart < n - 1;
    }
};

class Solution:
    def canThreePartsEqualSum(self, arr: List[int]) -> bool:
        total = sum(arr)
        if total % 3 != 0:
            return False
        
        target = total // 3
        n = len(arr)
        prefix_sum = 0
        first_part = -1
        second_part = -1
        
        for i in range(n):
            prefix_sum += arr[i]
            if prefix_sum == target and first_part == -1:
                first_part = i
            elif prefix_sum == 2 * target and first_part != -1:
                second_part = i
                break
        
        return first_part != -1 and second_part != -1 and second_part < n - 1

public class Solution {
    public bool CanThreePartsEqualSum(int[] arr) {
        int total = arr.Sum();
        if (total % 3 != 0) return false;
        
        int target = total / 3;
        int n = arr.Length;
        int sum = 0;
        int firstPart = -1, secondPart = -1;
        
        for (int i = 0; i < n; i++) {
            sum += arr[i];
            if (sum == target && firstPart == -1) {
                firstPart = i;
            } else if (sum == 2 * target && firstPart != -1) {
                secondPart = i;
                break;
            }
        }
        
        return firstPart != -1 && secondPart != -1 && secondPart < n - 1;
    }
}

var canThreePartsEqualSum = function(arr) {
    const totalSum = arr.reduce((sum, num) => sum + num, 0);
    
    if (totalSum % 3 !== 0) {
        return false;
    }
    
    const targetSum = totalSum / 3;
    let currentSum = 0;
    let partsFound = 0;
    
    for (let i = 0; i < arr.length - 1; i++) {
        currentSum += arr[i];
        if (currentSum === targetSum) {
            partsFound++;
            if (partsFound === 2) {
                return true;
            }
            currentSum = 0;
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)只需要一次遍历数组，其中 n 为数组长度
空间复杂度O(1)只使用了常数个额外变量

相关题目