点击获取AI摘要

2918. 数组的最小相等和 M

给你两个由正整数和 0 组成的数组 nums1 和 nums2 。

你必须将两个数组中的所有 0 替换为严格正整数，并且满足两个数组中所有元素的和相等。

返回最小相等和，如果无法使两数组相等，则返回 -1 。

示例 1：

输入：nums1 = [3,2,0,1,0], nums2 = [6,5,0]
输出：12
解释：可以按下述方式替换数组中的 0 ：

用 2 和 4 替换 nums1 中的两个 0 。得到 nums1 = [3,2,2,1,4] 。

用 1 替换 nums2 中的一个 0 。得到 nums2 = [6,5,1] 。
两个数组的元素和相等，都等于 12 。可以证明这是可以获得的最小相等和。

示例 2：

输入：nums1 = [2,0,2,0], nums2 = [1,4]
输出：-1
解释：无法使两个数组的和相等。

提示：

1 <= nums1.length, nums2.length <= 10⁵
0 <= nums1[i], nums2[i] <= 10⁶

问题分析

1.输入

nums1、nums2：两个数组，元素是非负整数（包括 0 和正整数）。

2.要求

将两个数组中所有的 0，分别替换成 “严格的正整数”（即 ≥1），
替换后，两个数组的 元素和 必须相等，
并且这个相等后的和要尽可能小。

3.输出

如果能做到，让两个数组和相等且最小，返回这个最小的和；否则返回 -1。

算法思路

令

$s_1 =$ nums1 中所有 非零元素 的和；
$k_1 =$ nums1 中 0 的个数。

类似地，

$s_2 =$ nums2 中所有非零元素的和；
$k_2 =$ nums2 中 0 的个数。

例如，若 nums1 = [3,2,0,1,0]，则

$s_1 = 3 + 2 + 1 = 6$ ，
$k_1 = 2$ 。

推导最小可行总和 $S$

设最终我们把 nums1 的所有 0 替换后，该数组的总和为 $S$ 。

nums1 已有非零部分和是 $s_1$ ，还有 $k_1$ 个 0，每个至少要替换成 1，
因此替换后总和至少是

$s_1 + (1 + 1 + \cdots + 1)\;(\text{共 }k_1\text{ 个}) = s_1 + k_1.$

同理，nums2 的替换后最小和是 $s_2 + k_2$ 。

要想两边都能达到同一个目标和 $S$ ，这个 $S$ 至少要满足：

$s_1 + k_1 \quad\text{且}\quad S \;\ge\; s_2 + k_2.$

因此最小的可行值，就是两者中的最大值：

$S = \max\bigl(s_1 + k_1,\; s_2 + k_2\bigr).$

无法达到

如果某个数组本身没有 0（即 $k_i=0$ ），那它就没法通过替换 0 来调整和。

例如，如果 nums1 本来就没有 0，而且非零和 $s_1$ 与目标 $S$ 不相等，那么就 不可能 让它变成 $S$ 。

这时应直接返回 -1。

时间复杂度

时间复杂度：遍历两数组各一次，做常数级的加减比较，因此时间复杂度为 $O(n_1 + n_2)$ ，其中 $n_1$ 、 $n_2$ 分别是两个数组长度。

空间复杂度： $O(1)$ （只使用了常数个辅助变量）。

代码分解

遍历 nums1
- 累加非零元素求和得到 $s_1$ ；
- 同时计数 0 的个数得到 $k_1$ 。
遍历 nums2
- 同理得到 $s_2$ 和 $k_2$ 。
计算目标和

$S = \max(s_1 + k_1,\;\; s_2 + k_2).$

检查不可调整情形
- 若 $(k_1 == 0 \land s_1 \neq S)$ ，或
- 若 $(k_2 == 0 \land s_2 \neq S)$ ，
  则返回 $-1$ 。
否则，返回 $S$ 。

代码实现

class Solution:
    def minSum(self, nums1: list[int], nums2: list[int]) -> int:
        # 1. 计算两个数组的非零之和与 0 的个数
        s1 = sum(x for x in nums1 if x != 0)
        k1 = nums1.count(0)
        s2 = sum(x for x in nums2 if x != 0)
        k2 = nums2.count(0)
        
        # 2. 最小可行的目标总和
        S = max(s1 + k1, s2 + k2)
        
        # 3. 如果某边无法通过替换 0 来达到 S，则不可行
        if (k1 == 0 and s1 != S) or (k2 == 0 and s2 != S):
            return -1
        
        # 4. 否则 S 就是最小相等和
        return S