2025. Partitions Count

Maximum Number of Ways to Partition an Array

非常烧脑的一题 我其实前八次尝试全错😆

那时候对于明显复杂的题目

比如通过率才36%左右的2025题

很容易陷入乱枪打鸟

我后来才懂得踩刹车 冷静观察再动手

Max Partitions Count的出厂值

题目有说 我们能选择什么元素都不动

首先就拿原始那长度$n$的数组来看

有多少个$1 \leq i < n$的索引$i$做到

$sum(nums[:i]) = sum(nums[i:])$

因此Max Partitions Count的出厂值

便是$C = \Sigma_{i = 1}^{n - 1} 1(sum(nums[:i]) = sum(nums[i:]))$

难在能去改某一索引上的元素

然而题目还有说 我们也能选择 刚好一个 索引$j$

把索引$j$上的元素改成输入的变量$k$

言下之意 便是我们得看看究竟哪个$j$能够

$C' = max_{j} \Sigma_{i = 1}^{n - 1} 1(sum(nums'[:i]) = sum(nums'[i:]))$

$nums'$和$nums$唯一的区别就在$nums'[j] = k$

最后再回传$max(C, C')$作为答案

寻找C'

前后缀差值的概念

首先储备一个叫做rightDiffCounts的哈希表

还有叫做pivotIdx的索引 题目有定义

pivotIdx必须从1开始 且小于$n$

因此pivotIdx沿著1一路访问到$n - 1$的路上

要计算 前后缀差值 $D =$ sum(nums[:pivotIdx]) - sum(nums[pivotIdx:])

并在rightDiffCounts纪录该$D$出现的次数

这前后缀差值有什么用呢？想像一下

要是 某个小于pivotIdx的索引$l$ 被选中

$nums[l]$被改成了$k$ 而且$nums[l] - k = D$

这样岂不让sum(nums[:pivotIdx]) - sum(nums[pivotIdx:])变成零？

pivotIdx因这么改而成为合法的分割点 C'增加1

左右对称的陷阱

不过还得再留意到一件事

就是某个$l$索引 其$nums[l]$变成$k$后

能因此成为合法分割点的索引 可能在$l$左 可能在$l$右

光靠rightDiffCounts只纪录分割点在$l$右 造成的前后缀差值

仍须leftDiffCounts管理分割点在$l$左 造成的前后缀差值

最终计数的遍历流程

前缀视角

负责遍历的索引$l$ 且$0 \leq l < n$

每次都去计算看看 当$nums[l]$被改成$k$后

$l$右边有多少个前后缀差值为$nums[l] - k$的分割点

$nums[l]$的更动 在$l$右边分割点视角 属前缀和变化

计数靠rightDiffCounts查$nums[l] - k$即可

后缀视角

相似的对称性来看 $nums[l]$更动成$k$

对于$l$左边的潜在分割点视角 属于后缀和变化

得统计$l$左边有多少个前后缀差值为$k - nums[l]$的分割点

计数靠leftDiffCounts查$k - nums[l]$即可

因此$nums[l]$改成$k$ 能造出的完美分割点数量就是

$C'_l$ = leftDiffCounts[k - nums[l]] + rightDiffCounts[nums[l] - k]

藉此和已知的历史最大值$C$比较 企图更新$C$

这边主要得注意的就是 因为是前缀与后缀

查询的差值正好差一个负号

随时更新两张哈希表

$l$被访问完后 算出$D_l = \text{sum}(nums[:l + 1]) - \text{sum}(nums[l + 1:])$

把$D_l$在rightDiffCounts的计数减1

把$D_l$在leftDiffCounts的计数加1

因为对于比$l$大的所有索引 它们的视角来讲

$l$只可能做左方分割点 不可能做右方的

C++

#include <unordered_map>
#include <vector>
using namespace std;

int countMaxPartitions(vector<int>& nums, int k) // LeetCode Q.2025.
{
    long long totalSum = 0; // Prevents overflow.
    for (const auto& num : nums)
        totalSum += num;

    // Left diff: only consider potential pivot indices at left side.
    // Right diff: only consider potential pivot indices at right side.
    // Map key: diff = prefix sum - suffix sum.
    unordered_map<long long, int> leftDiffCounts, rightDiffCounts;

    // Default to natural value: leave entire array unchanged.
    int maxPartitionWays = 0;

    long long prefixSum = 0;
    for (int pivotIdx = 1; pivotIdx < nums.size(); pivotIdx++) {
        prefixSum += nums[pivotIdx - 1];
        long long suffixSum = totalSum - prefixSum;
        rightDiffCounts[prefixSum - suffixSum]++;

        // Born as a great partition. No need to change.
        if (prefixSum == suffixSum)
            maxPartitionWays++;
    }

    prefixSum = 0; // Reset to let next for loop sweep again.

    for (int idx = 0; idx < nums.size(); idx++) {
        int num = nums[idx];
        prefixSum += num;

        int partitionWays = 0;

        // Potential pivot idx is at the right of current idx.
        partitionWays += rightDiffCounts[num - k];

        // Potential pivot idx is at the left of current idx.
        partitionWays += leftDiffCounts[k - num];

        if (partitionWays > maxPartitionWays)
            maxPartitionWays = partitionWays;

        long long diff = 2 * prefixSum - totalSum; // Prefix - suffix.

        // For future indices, this diff is only available as left side.
        leftDiffCounts[diff]++;
        rightDiffCounts[diff]--;
    }

    return maxPartitionWays;
}

Python

def count_max_partitions(nums: list[int], k: int) -> int:  # LeetCode Q.2025.
    # Left diff: only consider potential pivot indices at left side.
    # Right diff: only consider potential pivot indices at right side.
    # Dict key: diff = prefix sum - suffix sum.
    left_diff_counts: dict[int, int] = dict()
    right_diff_counts: dict[int, int] = dict()

    # Default to natural value: leave entire array unchanged.
    max_partition_ways = 0

    total_sum = sum(nums)
    prefix_sum = 0

    for pivot_idx in range(1, len(nums)):
        prefix_sum += nums[pivot_idx - 1]
        suffix_sum = total_sum - prefix_sum

        diff = prefix_sum - suffix_sum

        if diff not in right_diff_counts.keys():
            right_diff_counts[diff] = 0
        right_diff_counts[diff] += 1

        # Born as a great partition. No need to change.
        if prefix_sum == suffix_sum: max_partition_ways += 1

    prefix_sum = 0  # Reset to let next for loop sweep again.

    for idx, num in enumerate(nums):
        prefix_sum += num

        partition_ways = 0

        # Potential pivot idx is at the right of current idx.
        partition_ways += right_diff_counts.get(num - k, 0)

        # Potential pivot idx is at the left of current idx.
        partition_ways += left_diff_counts.get(k - num, 0)

        if partition_ways > max_partition_ways:
            max_partition_ways = partition_ways

        diff = 2 * prefix_sum - total_sum  # Prefix - suffix.
        # For future indices, this diff is only available as left side.

        if diff not in left_diff_counts.keys():
            left_diff_counts[diff] = 0
        left_diff_counts[diff] += 1

        if diff in right_diff_counts.keys():
            right_diff_counts[diff] -= 1

    return max_partition_ways

时间复杂度$O(n)$ 空间也是$O(n)$

这题逻辑确实蛮复杂的 会需要想好几遍才抓到命脉