05 August 2008
分割数组的最多方案数
给你一个下标从 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 。
前缀和 + 无序字典统计
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public int waysToPartition(int[] nums, int k) {
int n = nums.length;
long[] presum = new long[n + 1];
for (int i = 0; i < n; i++) {
presum[i + 1] = presum[i] + (long) nums[i];
}
Map<Long, Integer> dicR = new HashMap<>();
for (int i = 1; i < n; i++) {
long L = presum[i];
long R = presum[n] - presum[i];
dicR.put(R - L, dicR.getOrDefault(R - L, 0) + 1);
}
//----不改成k的情况
int res = dicR.getOrDefault(0L, 0);
//----改成k的情况
Map<Long, Integer> dicL = new HashMap<>();
for (int i = 0; i < n; i++) {
long add = k - nums[i];
int iL = dicL.getOrDefault(-add, 0);
int iR = dicR.getOrDefault(add, 0);
res = Math.max(res, iL + iR);
long diff = presum[n] - 2 * presum[i + 1];
dicR.put(diff, dicR.getOrDefault(diff, 0) - 1);
dicL.put(diff, dicL.getOrDefault(diff, 0) + 1);
}
return res;
}
}