What is the main pattern used in Minimum Equal Sum of Two Arrays After Replacing Zeros?

The main pattern is greedy choice plus invariant validation, where zeros are incrementally adjusted to match sums efficiently.

Can we replace zeros with values other than 1 initially?

Yes, but starting with 1 ensures minimal increments and simplifies the greedy approach while preserving the sum invariant.

What happens if one array has no zeros and a smaller sum?

It is impossible to equalize sums, and the function should return -1 immediately.

What is the time complexity of this solution?

The time complexity is O(n + m) since every element is visited once for initialization and potential adjustments.

How does the greedy approach guarantee the minimal equal sum?

By always increasing the smallest-sum array's zeros by the minimal required amount, we prevent overshooting and ensure the sum stays as low as possible.

#2918

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

数组的最小相等和

给你两个由正整数和 0 组成的数组 nums1 和 nums2 。你必须将两个数组中的所有 0 替换为严格正整数，并且满足两个数组中所有元素的和相等。返回最小相等和，如果无法使两数组相等，则返回 -1 。示例 1：输入： nums1 = [3,2,0,1,0], nums2 …

数组贪心

题目描述

给你两个由正整数和 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⁶

lightbulb

解题思路

方法一：分情况讨论

我们记把数组中的 $0$ 视为 $1$ ，统计两个数组的和，分别记为 $s_1$ 和 $s_2$ 。不妨设 $s_1 \le s_2$ 。

如果 $s_1 = s_2$ ，那么答案就是 $s_1$ 。
如果 $s_1 \lt s_2$ ，那么 $nums1$ 中必须存在 $0$ ，才能使得两个数组的和相等，此时的答案就是 $s_2$ 。否则，说明无法使两个数组的和相等，返回 $-1$ 。

时间复杂度 $O(n + m)$ ，其中 $n$ 和 $m$ 分别是数组 $nums1$ 和 $nums2$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def minSum(self, nums1: List[int], nums2: List[int]) -> int:
        s1 = sum(nums1) + nums1.count(0)
        s2 = sum(nums2) + nums2.count(0)
        if s1 > s2:
            return self.minSum(nums2, nums1)
        if s1 == s2:
            return s1
        return -1 if nums1.count(0) == 0 else s2

speed

复杂度分析

指标	值
时间	complexity is O(n + m) because each element in both arrays is processed once. Space complexity is O(1) since only sum tracking and incremental adjustments are needed, no extra data structures proportional to input size are used.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
They may ask why greedy adjustment ensures minimal sum rather than random replacements.
question_mark
Expect discussion on edge cases where an array has no zeros but a smaller sum.
question_mark
They might check if your approach scales for arrays of length 10^5 with high element values.

warning

常见陷阱

外企场景

error
Replacing zeros with arbitrary large numbers instead of minimal increments, missing the minimal sum.
error
Ignoring arrays with no zeros, leading to incorrect -1 detection.
error
Failing to update sums correctly after each greedy increment, causing wrong final sums.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow zeros to be replaced with any integer including zero, changing the greedy strategy to account for non-positive replacements.
arrow_right_alt
Instead of minimizing sum, maximize sum equality with constraints on maximum allowed element value.
arrow_right_alt
Work with more than two arrays, extending greedy adjustments to multiple sums while maintaining the minimal total sum.

help

常见问题

外企场景

继续练习

#2910 合法分组的最少组数 #2931 购买物品的最大开销 #2900 最长相邻不相等子序列 I