分割数组的方案数

标签: 数组 前缀和

难度: Medium

给你一个下标从 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 <= 105
  • -105 <= nums[i] <= 105

Submission

运行时间: 70 ms

内存: 31.1 MB

class Solution:
    def waysToSplitArray(self, nums: List[int]) -> int:
        a = list(accumulate(nums))
        p = a.pop() / 2
        return sum(i >= p for i in a)

Explain

此题解使用了前缀和的方法来简化数组分割点的计算。首先，使用Python内置的accumulate函数计算数组nums的前缀和，这样每个元素a[i]代表从nums[0]到nums[i]的元素和。接着，计算整个数组的总和并除以2，得到p，这是因为如果前半部分和大于等于后半部分和，那么前半部分和至少应该达到总和的一半。最后，遍历前缀和数组，计算有多少个元素的值大于等于p，这些元素对应的索引就是合法分割点的位置。

时间复杂度: O(n)

空间复杂度: O(n)

# Definition of the Solution class with a method to calculate the number of valid splits in the array

class Solution:
    def waysToSplitArray(self, nums: List[int]) -> int:
        # 计算数组的前缀和
        a = list(accumulate(nums))
        # 计算总和的一半，用于比较
        p = a.pop() / 2
        # 统计前缀和中大于等于总和一半的元素数量，即为合法分割的方案数
        return sum(i >= p for i in a)

Explore

在数组分割问题中，目标是找到一个点将数组分为两部分，使得前半部分的和至少与后半部分相等或更大。将总和除以2得到的p是总和的一半，如果前缀和达到或超过这个值p，说明从数组的起始位置到当前位置的元素总和已足够大，至少与剩余部分相等。因此，p作为比较基准，可以帮助我们快速定位到可能的分割点。

前缀和数组a中的每个元素a[i]代表从数组第一个元素到第i个元素的总和。通过比较每个前缀和a[i]与p（总和的一半）的关系，可以确定分割点。如果a[i]大于等于p，那么i就是一个可能的分割点，因为这意味着从数组开始到元素i的部分至少和剩下的元素总和相等。遍历前缀和数组，对每个满足条件的a[i]进行计数，即可得到所有可能的分割点数量。

计算前缀和时确实需要考虑数组中负数的存在，因为负数会影响到累积的总和。然而，前缀和的计算本质上是连续相加，无论元素是正数还是负数，都会正确反映从数组开始到当前元素的总和。负数会减少总和，这可能会影响分割点的位置，但只要按照算法逐个检查前缀和数组中的每个元素与p的关系，就能准确找到所有可能的分割点。

Python中的`accumulate`函数来自itertools模块，它通过应用给定的二元函数（默认为加法）来累积输入的迭代器（如列表）中的元素。具体到此问题，`accumulate`函数从第一个元素开始，依次将数组中的每个元素加到累积和中，并生成一个新的迭代器，其中包含从起始到当前元素的所有累积和。这种方式非常适合此问题，因为它能高效生成前缀和数组，这是分析和确定分割点所必需的。