2918. 数组的最小相等和

1. 题目链接

2918. 数组的最小相等和 - 力扣（LeetCode）

2. 题目描述

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

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

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

3. 题目示例

示例 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
解释：无法使两个数组的和相等。

4. 解题思路

1. 问题理解：
   • 给定两个数组nums1和nums2，可以将数组中的0替换为任意正整数。
   • 目标是通过替换0，使得两个数组的元素和相等，求这个相等的和的最小值。
   • 如果无法使两个数组的和相等，则返回-1。
2. 关键思路：
   • 计算数组和：对于每个数组，计算其元素和，其中0可以替换为1（最小值），因此每个0贡献1到总和中。
   • 检查可行性：
     • 如果一个数组没有0且其和小于另一个数组的和，则无法通过替换0来平衡，因为只能增加有0数组的和。
     • 否则，可以通过替换0来平衡两个数组的和。
   • 最小和：平衡后的和是两个数组和中的较大值，因为较小的和需要通过替换0增加到较大的和。
3. 算法流程：
   • 使用calc方法计算每个数组的和和是否包含0。
   • 检查是否可以平衡两个数组的和。
   • 返回平衡后的和（即较大的和）。

5. 题解代码

class Solution {
    // 定义一个内部记录类Pair，包含sum和zero两个字段
    private record Pair(long sum, boolean zero) {}

    public long minSum(int[] nums1, int[] nums2) {
        // 计算两个数组的sum和是否包含0
        Pair p1 = calc(nums1);
        Pair p2 = calc(nums2);
        
        // 如果某个数组没有0且其sum小于另一个数组的sum，则无法平衡
        if(!p1.zero && p1.sum < p2.sum || !p2.zero && p2.sum < p1.sum){
            return -1;
        }

        // 返回两个sum中的较大值
        return Math.max(p1.sum, p2.sum);
    }

    // 计算数组的sum和是否包含0
    private Pair calc(int[] nums){
        long sum = 0;
        boolean zero = false;
        for(int x : nums){
            if(x == 0){
                zero = true; // 标记存在0
                sum++; // 0可以替换为1，所以sum加1
            } else {
                sum += x; // 非0直接累加
            }
        }
        return new Pair(sum, zero);
    }
}

6. 复杂度分析

1. 时间复杂度：
   • 计算两个数组的和和是否包含0：O(n + m)，其中n和m分别是nums1和nums2的长度。
   • 比较和检查可行性：O(1)。
   • 总时间复杂度：O(n + m)。
2. 空间复杂度：
   • 使用了常数空间存储Pair对象和临时变量。
   • 总空间复杂度：O(1)。