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

🟢   🔖  贪心 数组  🔗 力扣 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	找到数组的中间位置	[✓]	数组 前缀和	🟢	🀄️ 🔗