分割数组的最多方案数

标签: 数组 哈希表 计数 枚举 前缀和

难度: Hard

给你一个下标从 0 开始且长度为 n 的整数数组 nums 。分割 数组 nums 的方案数定义为符合以下两个条件的 pivot 数目：

  • 1 <= pivot < n
  • nums[0] + nums[1] + ... + nums[pivot - 1] == nums[pivot] + nums[pivot + 1] + ... + nums[n - 1]

同时给你一个整数 k 。你可以将 nums 中 一个 元素变为 k 或 不改变 数组。

请你返回在 至多 改变一个元素的前提下，最多 有多少种方法 分割 nums 使得上述两个条件都满足。

示例 1：

输入：nums = [2,-1,2], k = 3
输出：1
解释：一个最优的方案是将 nums[0] 改为 k 。数组变为 [3,-1,2] 。
有一种方法分割数组：
- pivot = 2 ，我们有分割 [3,-1 | 2]：3 + -1 == 2 。

示例 2：

输入：nums = [0,0,0], k = 1
输出：2
解释：一个最优的方案是不改动数组。
有两种方法分割数组：
- pivot = 1 ，我们有分割 [0 | 0,0]：0 == 0 + 0 。
- pivot = 2 ，我们有分割 [0,0 | 0]: 0 + 0 == 0 。

示例 3：

输入：nums = [22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14], k = -33
输出：4
解释：一个最优的方案是将 nums[2] 改为 k 。数组变为 [22,4,-33,-20,-15,15,-16,7,19,-10,0,-13,-14] 。
有四种方法分割数组。

提示：

  • n == nums.length
  • 2 <= n <= 105
  • -105 <= k, nums[i] <= 105

Submission

运行时间: 718 ms

内存: 42.4 MB

class Solution:
    def waysToPartition(self, nums: List[int], k: int) -> int:
        n = len(nums)
        s = [nums[0]] * n
        right = defaultdict(int)
        for i in range(1, n):
            s[i] = s[i - 1] + nums[i]
            right[s[i - 1]] += 1

        ans = 0
        if s[-1] % 2 == 0:
            ans = right[s[-1] // 2]

        left = defaultdict(int)
        for v, x in zip(s, nums):
            d = k - x
            if (s[-1] + d) % 2 == 0:
                t = left[(s[-1] + d) // 2] + right[(s[-1] - d) // 2]
                if ans < t:
                    ans = t
            left[v] += 1
            right[v] -= 1
        return ans

Explain

本题解的思路基于前缀和的概念。首先，计算数组nums的前缀和数组s。接着，使用两个哈希表left和right来记录在当前位置左侧和右侧各个前缀和出现的次数。对于数组中的每个位置，检查通过替换当前位置的元素为k后，是否存在一种分割方式，使得左右两部分的和相等。如果存在，则更新最大分割方案数。最后，返回最大的分割方案数。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def waysToPartition(self, nums: List[int], k: int) -> int:
        n = len(nums)
        s = [nums[0]] * n  # 初始化前缀和数组
        right = defaultdict(int)
        for i in range(1, n):
            s[i] = s[i - 1] + nums[i]  # 计算前缀和
            right[s[i - 1]] += 1  # 更新右侧前缀和计数

        ans = 0
        if s[-1] % 2 == 0:
            ans = right[s[-1] // 2]  # 检查初始分割方案数

        left = defaultdict(int)
        for v, x in zip(s, nums):
            d = k - x
            if (s[-1] + d) % 2 == 0:
                t = left[(s[-1] + d) // 2] + right[(s[-1] - d) // 2]  # 检查替换后的分割方案数
                if ans < t:
                    ans = t
            left[v] += 1  # 更新左侧前缀和计数
            right[v] -= 1  # 更新右侧前缀和计数
        return ans

Explore

使用哈希表记录前缀和的出现次数的方法完全可以处理数组中存在负数或零的情况。前缀和是指从数组的第一个元素开始到当前元素的所有元素的累加和，因此无论元素值是正数、负数还是零，前缀和都能正确计算并记录。每个前缀和作为哈希表的键，不影响其计数功能。总体来说，数组中元素的具体值（正数、负数、零）不会影响前缀和的计算逻辑，只会影响最终的前缀和值，而哈希表正是用来根据这些值进行计数的，因此这种方法是有效的。

如果数组的总和（即s[-1]）是偶数，那么存在一种可能将数组分割成两个和相等的部分，因为只有当总和是偶数时，总和的一半（s[-1] / 2）也是一个整数，这是将总和平均分配到两个部分的前提。如果总和是奇数，则不可能将其平均分成两个相等的整数部分，因此在总和为奇数的情况下，无需检查初始分割方案数。这是因为不存在一个有效的分割点使得两部分的和相等。

在遍历数组时，同时更新左侧和右侧的哈希表是为了保持对各部分前缀和出现次数的准确记录。左侧哈希表记录从数组开始到当前元素的前缀和的出现次数，而右侧哈希表记录当前元素之后的前缀和的出现次数。这样做的目的是为了在考虑每个可能的分割点时，能够快速查询任何给定的前缀和在左侧和右侧出现的次数。当考虑替换任一元素后，这种动态更新策略允许我们有效地重新计算可能的分割方案数，而无需重新遍历整个数组。这对于保持算法效率至关重要。