leetcode2025. 分割数组的最多方案数-hard

1 题目：分割数组的最多方案数

官方标定难度：难

给你一个下标从 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<=10^5$
$-10^5<=k,nums[i]<=10^5$

2 solution

求前缀和，查找前缀和为总和一半的个数，由于改变某个元素时，部分前缀和已经改变，所以需要维持两个前缀和 map，一个是改变的元素之前的map，另一个是之后的 map，然后依次更新两个 map 并统计最大频数

代码

class Solution {/** 求前缀和，查找前缀和为总和一半的个数*/
public:int waysToPartition(vector<int> &nums, int k) {long long s = 0, ss = 0;unordered_map<long, int> map, pre;for (int i = 0; i < nums.size() - 1; i++) {s += nums[i];map[s]++;}s += nums.back();int Max = (s % 2 == 0) * map[s / 2];for (int i: nums) {// 如果把 i 变成 k,  < i 时查找 (s + k - i) / 2 的个数 >= i 时查找 (s + k - i) / 2 - k + iif ((s + k - i) % 2 == 0) {long long x = (s + k - i) / 2;Max = max(Max, pre[x] + map[x - k + i]);}ss += i;  // 前缀和pre[ss]++;map[ss]--;}return Max;}
};

结果