class Solution {
public:
int waysToPartition(vector<int>& nums, int k) {
}
};
2025. 分割数组的最多方案数
给你一个下标从 0 开始且长度为 n 的整数数组 nums 。分割 数组 nums 的方案数定义为符合以下两个条件的 pivot 数目：
1 <= pivot < nnums[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.length2 <= n <= 105-105 <= k, nums[i] <= 105原站题解
python3 解法, 执行用时: 1488 ms, 内存消耗: 44 MB, 提交时间: 2023-08-22 10:45:29
class Solution:
def waysToPartition(self, nums: List[int], k: int) -> int:
n, presum = len(nums), list(accumulate(nums))
left, right, total = defaultdict(int), Counter(presum[:n - 1]), presum[-1]
ans = right[total / 2]
for i in range(n):
if i > 0: left[presum[i - 1]] += 1
if i > 0: right[presum[i - 1]] -= 1
leftx = (total - nums[i] + k) / 2
rightx = total / 2 - (k - nums[i]) / 2
ans = max(ans, left[leftx] + right[rightx])
return ans
cpp 解法, 执行用时: 588 ms, 内存消耗: 247.4 MB, 提交时间: 2023-08-22 10:35:12
using ll = long long;
class Solution {
public:
int waysToPartition(vector<int>& nums, int k) {
int n = nums.size(), ans = 0;
vector<ll> sum(n);
sum[0] = nums[0];
unordered_map<ll, int> cl, cr;
for (int i = 1; i < n; ++i) {
sum[i] = sum[i - 1] + nums[i];
cr[sum[i - 1]]++;
}
ll tot = sum[n - 1];
if (tot % 2 == 0) ans = cr[tot / 2];
//cl表示当修改nums[i]为k时，分隔位pivot小于i存放的前缀和，同理cr表示大于或者等于。
for (int i = 0; i < n; ++i) {
int dif = k - nums[i];
if ((tot + dif) % 2 == 0) {
//cr + dif == (tot + dif) / 2,因为cr的前缀和都包含了修改前的nums[i]
ans = max(ans, cl[(tot + dif) / 2] + cr[(tot - dif) / 2]);
}
cl[sum[i]]++;
cr[sum[i]]--;
}
return ans;
}
};
golang 解法, 执行用时: 332 ms, 内存消耗: 19.2 MB, 提交时间: 2023-08-22 10:34:26
func waysToPartition(nums []int, k int) (ans int) {
n := len(nums)
sum := make([]int, n)
sum[0] = nums[0]
cntR := map[int]int{}
for i := 1; i < n; i++ {
sum[i] = sum[i-1] + nums[i] // 前缀和
cntR[sum[i-1]]++ // 右前缀和个数
}
tot := sum[n-1]
if tot%2 == 0 {
ans = cntR[tot/2] // 不修改
}
cntL := map[int]int{} // // 左前缀和个数
for i, s := range sum {
if d := k - nums[i]; (tot+d)%2 == 0 {
ans = max(ans, cntL[(tot+d)/2]+cntR[(tot-d)/2]) // 修改 nums[i]
}
cntL[s]++
cntR[s]--
}
return
}
func max(a, b int) int { if b > a { return b }; return a }