【每日一题见微知著】分割数组的最多方案数
class Solution {
public int waysToPartition(int[] nums, int k) {
int n = nums.length;
int[] preSum = new int[n + 1];
Map<Integer, Integer> m1 = new HashMap<>();
Map<Integer, Integer> m2 = new HashMap<>();
for (int i = 1; i <= n; i++) {
preSum[i] = nums[i - 1] + preSum[i - 1];
// 一开始除了最后一个前缀和，其余均在m2中
if (i != n) m2.put(preSum[i], m2.getOrDefault(preSum[i], 0) + 1);
}
int ans = 0;
if (preSum[n] % 2 == 0) {
// 若一个元素都不修改
ans = m2.getOrDefault(preSum[n] / 2, 0);
}
for (int i = 0; i < n; i++) {
// 修改下标为i的元素变成k
int change = k - nums[i];
// 所有元素总和的变化量也是change
int pn = preSum[n] + change;
if (pn % 2 == 0) {
// 在m1中我们要找的目标是 target1 = 总和/2 的数量
int t1 = pn / 2;
// 在m2中我们要找的目标是 target2 = target1 - change 的数量
int t2 = t1 - change;
int found = m1.getOrDefault(t1, 0) + m2.getOrDefault(t2, 0);
ans = Math.max(ans, found);
}
// 不断减少m2中的计数，增加m1对应的计数
if (i != n - 1) {
m1.put(preSum[i + 1], m1.getOrDefault(preSum[i + 1], 0) + 1);
int tmp = m2.get(preSum[i + 1]);
if (tmp == 1) {
m2.remove(preSum[i + 1]);
} else {
m2.put(preSum[i + 1], tmp - 1);
}
}
}
return ans;
}
}
//
class Solution {
public int waysToPartition(int[] nums, int k) {
int n=nums.length;
Map<Long,Integer> pre=new HashMap<>();
Map<Long,Integer> curA=new HashMap<>();
long[] prefix=new long[n];
for(int i=0;i<n;i++){
if(i!=0){
prefix[i]+=(prefix[i-1]+nums[i]);
}
else{
prefix[i]=nums[i];
}
}
int max=0;
int count0=0;
pre.put((long)(k-nums[0]),0);
for(int i=1;i<n;i++){
long left=prefix[i-1];
long right=prefix[n-1]-left;
long c=right-left;
if(c==0){
count0++;
if(count0>max){
max=count0;
}
}
curA.put(c,curA.getOrDefault(c,0)+1);
int curMid=curA.getOrDefault((long)(nums[i]-k),0);
int preMid=pre.getOrDefault(c,-1)+1;
if(preMid!=0)
pre.put(c,preMid);
pre.put((long)(k-nums[i]),Math.max(pre.getOrDefault((long)(k-nums[i]),0),curMid));
if(max<Math.max(curMid,preMid)){
max=Math.max(curMid,preMid);
}
}
return max;
}
}