1013.md

title	description	keywords
1013. 将数组分成和相等的三个部分	LeetCode 1013. 将数组分成和相等的三个部分题解，Partition Array Into Three Parts With Equal Sum，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 1013. 将数组分成和相等的三个部分 将数组分成和相等的三个部分 Partition Array Into Three Parts With Equal Sum 解题思路 贪心 数组

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

🟢 Easy  🔖  贪心 数组  🔗 力扣 LeetCode

题目

Given an array of integers arr, return true if we can partition the array into three non-empty parts with equal sums.

Formally, we can partition the array if we can find indexes i + 1 < j with (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1])

Example 1:

Input: arr = [0,2,1,-6,6,-7,9,1,2,0,1]

Output: true

Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

Example 2:

Input: arr = [0,2,1,-6,6,7,9,-1,2,0,1]

Output: false

Example 3:

Input: arr = [3,3,6,5,-2,2,5,1,-9,4]

Output: true

Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

Constraints:

• 3 <= arr.length <= 5 * 10^4
• -10^4 <= arr[i] <= 10^4

题目大意

给你一个整数数组 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. 计算数组的总和 totalSum，如果 totalSum 不能被 3 整除，直接返回 false，因为三个部分的和无法相等。

2. 每个部分的目标和为 target = totalSum / 3，我们需要找到三个这样的部分，使它们的和等于 target。

3. 寻找分割点：

   • 从左到右遍历数组，累加元素的值到 partSum。
   • 每当累加和等于目标和 target 时，说明可以分割出一个部分。
   • 重置累加和 partSum = 0，继续寻找下一个部分。
   • 当找到三个部分时，如果还有元素没有遍历完，继续累加剩余的元素和到 partSum。

4. 如果遍历结束后，找到了三个部分，且剩余元素和 partSum == 0，返回 true；否则，返回 false。

复杂度分析

• 时间复杂度：O(n)，遍历数组两次，一次计算总和，一次寻找分割点。
• 空间复杂度：O(1)，仅使用常量级额外空间。

代码

/**
 * @param {number[]} arr
 * @return {boolean}
 */

    return count == 3 && sum == 0
};
var canThreePartsEqualSum = function (arr) {
	const totalSum = arr.reduce((acc, cur) => acc + cur, 0);

	// 如果总和不能被 3 整除，直接返回 false
	if (totalSum % 3 !== 0) return false;

	const target = totalSum / 3;
	let partSum = 0,
		count = 0;

	for (let num of arr) {
		partSum += num;
		if (partSum === target && count < 3) {
			count++;
			partSum = 0;
		}
	}

	// 如果正好被分为 3 部分，返回 true
	return count == 3 && partSum == 0;
};

相关题目

题号	标题	题解	标签	难度	力扣
1991	找到数组的中间位置	[✓]	数组 前缀和	🟢	🀄️ 🔗