2025：分割数组的最多方案数（2217 分）

力扣第 62 场双周赛第 4 题

题目

给你一个下标从 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

相似问题：

• 0416：分割等和子集
• 0698：划分为k个相等的子集

分析

• 容易想到先求出前缀和数组 P
• 不修改的情况，即是求 P[:-1] 中多少个等于 P[-1]/2
• 将 nums[i] 修改为 k 的话，增加了 add=k-nums[i]，总和变为 P[-1]+add
  • 注意修改后 P[:i] 不变，P[i:] 都将增加 add
  • 因此要求 P[:i] 中 (P[-1]+add)/2 的个数，P[i:-1] 中 (P[-1]-add)/2 的个数
• 用两个计数器分别维护 P[:i]，P[i:-1] 的计数即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def waysToPartition(self, nums: List[int], k: int) -> int:
        P = list(accumulate(nums))
        L,R = defaultdict(int),Counter(P[:-1])
        s = P[-1] 
        res = R[s//2] if s%2==0 else 0
        for x,p in zip(nums,P):
            add = k-x
            if (s+add)%2==0:
                res = max(res,L[(s+add)//2]+R[(s-add)//2])
            L[p] += 1
            R[p] -= 1
        return res

783 ms