2025. 分割数组的最多方案数

题目地址(2025. 分割数组的最多方案数)

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

题目描述

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

前置知识

  • 枚举

  • 前缀和

  • 哈希表

公司

  • 暂无

思路

题目让我们求经过一顿操作后最多满足左右和相等的索引 pivot 有多少个。

于是我们可以枚举所有的索引 i ,如果我将 i 的值改为 k 那么有多少 pivot。对于每一个 i,我们如何计算有多少 pivot 呢?

显然 pivot 是大于 0 的。

那么如何判断索引 1 是否是一个 pivot 呢?我们只需判断 pres[i-1] 是否等于 total / 2 即可。其中 pres 是 nums 的前缀和, total 是 nums 总和,也就是 sum(nums)。

那么如何判断索引 2 是否是一个 pivot 呢?还是类似的,判断 pres[i-1]是否等于 total / 2 即可。

可问题是 pres 发生了变化,具体来说 pres[2], pres[3] ... 都变了,变化的增幅也是一致的,同理 total 也是变化了。 total 变化倒容易求,新的 total = 旧的 total + k - nums[i] 其中 nums[i]为变化前的值。但是 pres 里一系列的值都变了,怎么搞?

其实我们可以这么做。以题目的 [2,-1,2] 为例:

  • 定义两个哈希表 left 和 right,分别表示当前遍历到的元素的左右侧的前缀和的映射,key 是前缀和的值, value 是出现次数。

  • left 初始化为空,right 初始化为 { 2: 1, 1: 1, 3: 1 },表示前缀和 2,1,3 分别出现了一次。

  • 根据 left,right 和 total 我们就能求出将当前索引值改为 k 的 pivot 总数了。left[total/2] + right[total/2]。 这是本题的第一个难点。

  • 接下来枚举所有的索引,枚举到下一项的是否如何更新 left, right 和 total 呢?这是本题的第二个难点。

  1. left[pres[i-1]] += 1 right[pres[i-1]] -= 1。前提是 i>0。

  2. 如果上一次结果是 left[total/2] + right[total/2],那么下一次是多少呢?答案是 left[(total - nums[i] + k) / 2] + right[total - (total - nums[i] + k) / 2])

其中 total - nums[i] + k 是左半部分新的 total,右半部分是 total - 左半部分新的 total。

关键点

  • 滚动思想

代码

  • 语言支持:Python3

Python3 Code:


class Solution:
    def waysToPartition(self, nums: List[int], k: int) -> int:
        n, pres = len(nums), list(accumulate(nums))
        left, right = defaultdict(int), Counter(pres[:n - 1])
        total = pres[-1]
        ans = right[total / 2]
        for i in range(n):
            if i > 0: left[pres[i - 1]] += 1
            if i > 0: right[pres[i - 1]] -= 1
            ans = max(ans, left[(total - nums[i] + k) / 2] + right[total - (total - nums[i] + k) / 2])
        return ans

复杂度分析

令 n 为数组长度。

  • 时间复杂度:$O(n)$

  • 空间复杂度:left 和 right 都不会超过 n 项,因此空间复杂度为 $O(n)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~s

以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。

最后更新于