2918. 数组的最小相等和

题目链接

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

题目描述

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

题解代码

classSolution{// 定义一个内部记录类Pair，包含sum和zero两个字段privaterecordPair(longsum,booleanzero){}publiclongminSum(int[]nums1,int[]nums2){// 计算两个数组的sum和是否包含0Pairp1=calc(nums1);Pairp2=calc(nums2);// 如果某个数组没有0且其sum小于另一个数组的sum，则无法平衡if(!p1.zero&&p1.sum<p2.sum||!p2.zero&&p2.sum<p1.sum){return-1;}// 返回两个sum中的较大值returnMath.max(p1.sum,p2.sum);}// 计算数组的sum和是否包含0privatePaircalc(int[]nums){longsum=0;booleanzero=false;for(intx:nums){if(x==0){zero=true;// 标记存在0sum++;// 0可以替换为1，所以sum加1}else{sum+=x;// 非0直接累加}}returnnewPair(sum,zero);}}

复杂度分析

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