原文链接: https://leetcode-cn.com/problems/maximum-number-of-ways-to-partition-an-array

英文原文

You are given a 0-indexed integer array nums of length n. The number of ways to partition nums is the number of pivot indices that satisfy both conditions:

• 1 <= pivot < n
• nums[0] + nums[1] + ... + nums[pivot - 1] == nums[pivot] + nums[pivot + 1] + ... + nums[n - 1]

You are also given an integer k. You can choose to change the value of one element of nums to k, or to leave the array unchanged.

Return the maximum possible number of ways to partition nums to satisfy both conditions after changing at most one element.

 

Example 1:

Input: nums = [2,-1,2], k = 3
Output: 1
Explanation: One optimal approach is to change nums[0] to k. The array becomes [3,-1,2].
There is one way to partition the array:
- For pivot = 2, we have the partition [3,-1 | 2]: 3 + -1 == 2.

Example 2:

Input: nums = [0,0,0], k = 1
Output: 2
Explanation: The optimal approach is to leave the array unchanged.
There are two ways to partition the array:
- For pivot = 1, we have the partition [0 | 0,0]: 0 == 0 + 0.
- For pivot = 2, we have the partition [0,0 | 0]: 0 + 0 == 0.

Example 3:

Input: nums = [22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14], k = -33
Output: 4
Explanation: One optimal approach is to change nums[2] to k. The array becomes [22,4,-33,-20,-15,15,-16,7,19,-10,0,-13,-14].
There are four ways to partition the array.

 

Constraints:

• n == nums.length
• 2 <= n <= 105
• -105 <= k, nums[i] <= 105

中文题目

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

通过代码

高赞题解

计算出 $\textit{nums}$ 的前缀和 $\textit{sum}$，记所有元素的和为 $\textit{tot}$。

对于不修改的情况，合法分割相当于要满足 $\textit{sum}[i] = \textit{tot}-\textit{sum}[i]$，即 $\textit{sum}[i]=\dfrac{\textit{tot}}{2}$。

对于修改的情况，枚举修改的元素，记变化量 $d=k-\textit{nums}[i]$，这一修改操作对于 $i$ 左侧的前缀和是没有影响的，因此合法分割相当于要满足 $\textit{sum}[i] = \textit{tot}+d-\textit{sum}[i]$，即 $\textit{sum}[i]=\dfrac{\textit{tot}+d}{2}$；而对于 $i$ 右侧的前缀和，每个前缀和都增加了 $d$，因此合法分割相当于要满足 $\textit{sum}[i]+d = \textit{tot}+d-(\textit{sum}[i]+d)$，即 $\textit{sum}[i]=\dfrac{\textit{tot}-d}{2}$。

我们可以在枚举 $\textit{nums}[i]$ 的同时，用两个哈希表动态维护 $i$ 左右前缀和的个数，从而做到对每个 $\textit{nums}[i]$ 在 $O(1)$ 的时间计算出合法分割数，因此总的时间复杂度为 $O(n)$。

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
}

统计信息

通过次数	提交次数	AC比率
1331	5109	26.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言