How do I approach the Equal Sum Arrays With Minimum Number of Operations problem?

You should focus on balancing the sums of the two arrays using hash tables to track frequencies and applying a greedy approach to minimize operations.

What is the primary pattern for solving this problem?

The primary pattern involves array scanning plus hash lookup to track and modify array elements efficiently.

Can the problem be solved without hash tables?

While possible, using hash tables significantly optimizes the solution by reducing redundant checks and improving performance with larger input sizes.

What should I do if the arrays have different lengths?

The length difference doesn't affect the approach, but the sum difference must be considered when balancing the arrays.

What are some edge cases to consider for this problem?

Consider cases where it's impossible to balance the sums, such as when one array has much larger or smaller values and no valid operations can achieve equality.

#1775

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

通过最少操作次数使数组的和相等

给你两个长度可能不等的整数数组 nums1 和 nums2 。两个数组中的所有值都在 1 到 6 之间（包含 1 和 6 ）。每次操作中，你可以选择任意数组中的任意一个整数，将它变成 1 到 6 之间任意的值（包含 1 和 6 ）。请你返回使 nums1 中所有数的和与 nums2 中所…

数组哈希表贪心计数

题目描述

给你两个长度可能不等的整数数组 nums1 和 nums2 。两个数组中的所有值都在 1 到 6 之间（包含 1 和 6）。

每次操作中，你可以选择任意数组中的任意一个整数，将它变成 1 到 6 之间任意的值（包含 1 和 6）。

请你返回使 nums1 中所有数的和与 nums2 中所有数的和相等的最少操作次数。如果无法使两个数组的和相等，请返回 -1 。

示例 1：

输入：nums1 = [1,2,3,4,5,6], nums2 = [1,1,2,2,2,2]
输出：3
解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。
- 将 nums2[0] 变为 6 。 nums1 = [1,2,3,4,5,6], nums2 = [6,1,2,2,2,2] 。
- 将 nums1[5] 变为 1 。 nums1 = [1,2,3,4,5,1], nums2 = [6,1,2,2,2,2] 。
- 将 nums1[2] 变为 2 。 nums1 = [1,2,2,4,5,1], nums2 = [6,1,2,2,2,2] 。

示例 2：

输入：nums1 = [1,1,1,1,1,1,1], nums2 = [6]
输出：-1
解释：没有办法减少 nums1 的和或者增加 nums2 的和使二者相等。

示例 3：

输入：nums1 = [6,6], nums2 = [1]
输出：3
解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。
- 将 nums1[0] 变为 2 。 nums1 = [2,6], nums2 = [1] 。
- 将 nums1[1] 变为 2 。 nums1 = [2,2], nums2 = [1] 。
- 将 nums2[0] 变为 4 。 nums1 = [2,2], nums2 = [4] 。

提示：

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

lightbulb

解题思路

方法一：贪心 + 排序

我们用 $s_1$ 和 $s_2$ 分别表示数组 nums1 和 nums2 的和。

如果 $s_1 = s_2$ ，则不需要任何操作，直接返回 $0$ 。否则，我们不妨设 $s_1 \lt s_2$ ，即 $nums_1$ 中的元素和小于 $nums_2$ 中的元素和，那么两个数组元素和的差值 $d=s_2-s_1$ 。

要使得两个数组元素和相等，我们需要对 nums1 中的元素进行增大操作，对 nums2 中的元素进行减小操作。

对于 nums1 中的每个元素 $v$ ，我们最多可以将其增大到 $6$ ，那么 $v$ 可以增大的量为 $6-v$ 。对于 nums2 中的每个元素 $v$ ，我们最多可以将其减小到 $1$ ，那么 $v$ 可以减小的量为 $v-1$ 。

我们将每个元素的变化量放入数组 arr 中，然后对数组 arr 进行降序排列。

接下来，我们从数组 arr 的第一个元素开始，贪心地将 $d$ 减去每个元素的变化量，直到 $d \leq 0$ ，返回此时的操作次数即可。

遍历结束后，如果 $d \gt 0$ ，说明无法使得两个数组元素和相等，返回 $-1$ 。

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
        s1, s2 = sum(nums1), sum(nums2)
        if s1 == s2:
            return 0
        if s1 > s2:
            return self.minOperations(nums2, nums1)
        arr = [6 - v for v in nums1] + [v - 1 for v in nums2]
        d = s2 - s1
        for i, v in enumerate(sorted(arr, reverse=True), 1):
            d -= v
            if d <= 0:
                return i
        return -1

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Evaluate how efficiently the candidate uses hash tables to track frequencies of array elements.
question_mark
Check the candidate's ability to apply a greedy approach for minimal operations.
question_mark
Assess if the candidate considers edge cases where the sums cannot be equalized.

warning

常见陷阱

外企场景

error
Not considering cases where it is impossible to balance the sums, which should return -1.
error
Using an inefficient method to find the best elements to modify, resulting in higher-than-necessary operation counts.
error
Neglecting to check if the arrays' sums are already equal before proceeding with operations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the arrays have significantly larger sizes or different value ranges?
arrow_right_alt
How would the solution change if the value range of elements was increased beyond 1 to 6?
arrow_right_alt
Can this problem be solved by minimizing operations in a different order or sequence of changes?

help

常见问题

外企场景

继续练习

#1481 不同整数的最少数目 #2131 连接两字母单词得到的最长回文串 #2170 使数组变成交替数组的最少操作数