2270. 分割数组的方案数

🟠   🔖  数组 前缀和  🔗 力扣 LeetCode

题目

You are given a 0-indexed integer array nums of length n.

nums contains a valid split at index i if the following are true:

• The sum of the first i + 1 elements is greater than or equal to the sum of the last n - i - 1 elements.
• There is at least one element to the right of i. That is, 0 <= i < n - 1.

Return the number ofvalid splits in nums.

Example 1:

Input: nums = [10,4,-8,7]

Output: 2

Explanation:

There are three ways of splitting nums into two non-empty parts:

• Split nums at index 0. Then, the first part is [10], and its sum is 10. The second part is [4,-8,7], and its sum is 3. Since 10 >= 3, i = 0 is a valid split.
• Split nums at index 1. Then, the first part is [10,4], and its sum is 14. The second part is [-8,7], and its sum is -1. Since 14 >= -1, i = 1 is a valid split.
• Split nums at index 2. Then, the first part is [10,4,-8], and its sum is 6. The second part is [7], and its sum is 7. Since 6 < 7, i = 2 is not a valid split.

Thus, the number of valid splits in nums is 2.

Example 2:

Input: nums = [2,3,1,0]

Output: 2

Explanation:

There are two valid splits in nums:

• Split nums at index 1. Then, the first part is [2,3], and its sum is 5. The second part is [1,0], and its sum is 1. Since 5 >= 1, i = 1 is a valid split.
• Split nums at index 2. Then, the first part is [2,3,1], and its sum is 6. The second part is [0], and its sum is 0. Since 6 >= 0, i = 2 is a valid split.

Constraints:

• 2 <= nums.length <= 10^5
• -10^5 <= nums[i] <= 10^5

题目大意

给你一个下标从 0 开始长度为 n 的整数数组 nums 。
如果以下描述为真，那么 nums 在下标 i 处有一个 合法的分割 ：

• 前 i + 1 个元素的和 大于等于 剩下的 n - i - 1 个元素的和。
• 下标 i 的右边 至少有一个 元素，也就是说下标 i 满足 0 <= i < n - 1 。

请你返回 nums 中的 合法分割 方案数。

示例 1：

输入： nums = [10,4,-8,7]

输出： 2

解释：

总共有 3 种不同的方案可以将 nums 分割成两个非空的部分：

• 在下标 0 处分割 nums 。那么第一部分为 [10] ，和为 10 。第二部分为 [4,-8,7] ，和为 3 。因为 10 >= 3 ，所以 i = 0 是一个合法的分割。
• 在下标 1 处分割 nums 。那么第一部分为 [10,4] ，和为 14 。第二部分为 [-8,7] ，和为 -1 。因为 14 >= -1 ，所以 i = 1 是一个合法的分割。
• 在下标 2 处分割 nums 。那么第一部分为 [10,4,-8] ，和为 6 。第二部分为 [7] ，和为 7 。因为 6 < 7 ，所以 i = 2 不是一个合法的分割。

所以 nums 中总共合法分割方案受为 2 。

示例 2：

输入： nums = [2,3,1,0]

输出： 2

解释：

总共有 2 种 nums 的合法分割：

• 在下标 1 处分割 nums 。那么第一部分为 [2,3] ，和为 5 。第二部分为 [1,0] ，和为 1 。因为 5 >= 1 ，所以 i = 1 是一个合法的分割。
• 在下标 2 处分割 nums 。那么第一部分为 [2,3,1] ，和为 6 。第二部分为 [0] ，和为 0 。因为 6 >= 0 ，所以 i = 2 是一个合法的分割。

提示：

• 2 <= nums.length <= 10^5
• -10^5 <= nums[i] <= 10^5

解题思路

我们需要找到将数组 nums 分成左右两部分时，满足以下条件的分割点数量：

• 左部分的和 leftSum 大于等于右部分的和 rightSum。

直接计算 leftSum 和 rightSum 每次的值可能导致重复计算，因此可以利用以下关系优化计算：

• rightSum = totalSum - leftSum

我们可以通过维护 leftSum 和 totalSum 来避免重复计算，从而降低复杂度。

1. 计算总和：

   • 先计算数组的总和 totalSum。

2. 遍历数组：

   • 使用变量 leftSum 来记录左部分的和。
   • 遍历数组中的每个分割点（从索引 0 到 nums.length - 2），计算：
     • rightSum = totalSum - leftSum
   • 如果 leftSum >= rightSum，增加计数器 count。

3. 返回结果：

   • 返回满足条件的分割点数量。

复杂度分析

• 时间复杂度：O(n)，计算 totalSum 和 leftSum 需要遍历数组。
• 空间复杂度：O(1)，只使用了常量级额外空间。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var waysToSplitArray = function (nums) {
	let count = 0;
	let totalSum = nums.reduce((a, b) => a + b, 0);
	let leftSum = 0;

	for (let i = 0; i < nums.length - 1; i++) {
		leftSum += nums[i];
		if (leftSum >= totalSum - leftSum) {
			count++;
		}
	}

	return count;
};

相关题目

题号	标题	题解	标签	难度	力扣
410	分割数组的最大值		贪心 数组 二分查找 2+	🔴	🀄️ 🔗
724	寻找数组的中心下标	[✓]	数组 前缀和	🟢	🀄️ 🔗
1712	将数组分成三个子数组的方案数		数组 双指针 二分查找 1+	🟠	🀄️ 🔗
1991	找到数组的中间位置	[✓]	数组 前缀和	🟢	🀄️ 🔗
2035	将数组分成两个数组并最小化数组和的差		位运算 数组 双指针 4+	🔴	🀄️ 🔗
2256	最小平均差		数组 前缀和	🟠	🀄️ 🔗