Skip to content

Latest commit

 

History

History
133 lines (82 loc) · 4.92 KB

2025.maximum-number-of-ways-to-partition-an-array.md

File metadata and controls

133 lines (82 loc) · 4.92 KB
Raw

题目地址(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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

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