题目描述

给你两个长度可能不等的整数数组 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

方法一：我的方法，双指针 + 优化（确保不超时）

思路：

• 首先对两个数组分别求和，得到 sum1 和 sum2 ，计算得到两者差值的绝对值 diff；
• 然后通过比较确定 「总和较大和较小的数组」， 传入 函数 count ，返回最少操作次数；
• 在函数 count 中，对两个数组进行排序， 其中总和较大的数组 降序 ，方便减少总和 ；总和较小的数组 升序 ，方便增大总和。
• 之后开始使用 双指针 遍历两个数组，目标是使得差值 diff 为 0 ，判断当前元素与 1 或 6 的差值，选择差值较大的元素进行变换，以尽快使 diff = 0。
• 当其中一个数组中能遍历的元素都遍历完之后，就单独遍历剩余的数组；
• 最后已经完成了所有可能的变换，diff 仍然大于 0 ，那么不可能变换成功，因此 cnt = -1 。
• 否则返回当前的 cnt 。
• 该思路会出现 超时 的问题，此时需要进行优化，参考方法二。
  • 假设 nums1 的元素和小于 nums2 的元素和。
  • 把 nums1 的所有数都改为 6 ，nums2 的所有数都改成 1 ，如果 nums1 的元素和仍小于 nums2 的元素和，则说明无论怎么操作，都无法使这两个数组的元素和相等；

情况

• 优化前，不通过，只通过 58 / 65 的测试点，其余超时。
• 优化后，能通过；

收获

• 在处理数组边界的问题上花费了大量时间，以后要更注重下标范围。

时间复杂度：O（n log n）sort 函数的时间复杂度？【不确定】
空间复杂度：O（1）

class Solution {
public:int count(vector& nums_min, vector& nums_max, int diff){int cnt = 0;int p = 0, q = 0, a = 0, b = 0;int len1 = nums_min.size(), len2 = nums_max.size();// 优化        .// 如果总和较小的数组全变为6，总和较大的数组全变为1// 后者仍然大于前者，那么不可能变换成功if(len2 > 6 * len1) return -1;sort(nums_min.begin(), nums_min.end());sort(nums_max.begin(), nums_max.end(), greater());while(diff>0){if(p==len1 || q==len2 || nums_min[p]==6 || nums_max[q]==1) break;a = 6 - nums_min[p];b = nums_max[q] - 1;if(a > b){diff -= a;p ++;}else{diff -= b;q ++;}cnt ++;}// 遍历nums_max// 情况1:要么是nums_min全为6，要么是已经遍历到最后一个值if(p==len1 || p1){while(q < len2 && diff>0){b = nums_max[q] - 1;diff -= b;q ++;cnt ++;}}// 遍历nums_min// 情况1:要么是nums_max全为1，要么是已经遍历到最后一个值if(q == len2 ||pwhile(p0){a = 6 - nums_min[p];diff -= a;p ++;cnt ++;}}    if(diff>0) cnt = -1;return cnt;}int minOperations(vector& nums1, vector& nums2) {int cnt = 0; // 操作次数int sum1 = 0, sum2 = 0;// 求和for(auto& num : nums1)  sum1 += num;for(auto& num : nums2)  sum2 += num;int diff = abs(sum1 - sum2);// 目标：diff=0if(sum1 < sum2) cnt = count(nums1, nums2, diff);else cnt = count(nums2, nums1, diff);return cnt;}
};

方法二：哈希表/数组 + 算法优化

思路：

• 设 nums1 的元素和 小于 nums2 的元素和（如果不是则交换两个数组），元素和的差为 diff。
• 那么 nums1 的元素需要变大，nums2 的元素需要变小。
• 计算每个元素的 最大变化量：
  • nums1[i] 最大能变成 6 ，最大变化量为 6 - nums1[i] ；
  • nums2[i] 最小能变成 1 ，最大变化量为 num2[i] - 1；
• 统计这些变化量的个数， 记录到一个哈希表或长为 6 的数组 cnt 中，也就是有 cnt[i] 个数可以使 diff 减少 i。
• 从大到小枚举 i = 5，4，3，2，1：
  • 如果 d > i * cnt[i] ，那么应该把这 cnt[i] 个数的变化量拉满， 并更新 diff 为 diff - i * cnt[i];
  • 否则，可以通过需要其中的 ⌈diff / i​⌉ 个数，使 diff 恰好为 0 ，退出循环。
• 累加需要修改的个数，即为答案，如果无法使 diff = 0，返回 -1 。

优化

• 假设 nums1 的元素和小于 nums2 的元素和。
• 把 nums1 的所有数都改为 6 ，nums2 的所有数都改成 1 ，如果 nums1 的元素和仍小于 nums2 的元素和，则说明无论怎么操作，都无法使这两个数组的元素和相等；
• 对于 nums1 的元素和大于 nums2 的元素和的情况，也同理。
• 因此，设 n 为 nums1 的长度， m 为 nums2 的长度，我们可以在一开始就判断： 如果「6n < m」 或「6m < n」，直接返回 -1 。否则，一定可以使得两个数组相等，这事因为从「 nums1 的元素和小于 nums2 的元素和」 到 「nums1 的元素和 大于等于 nums2 的元素和」，由于元素值可以变成 [1，6] 的任意值，我们可以每次操作只把一个元素增大 1 或减小 1 ，这样必然会遇到元素和相差为 0 的情况。
  情况
• 通过；

收获

• 这个思路很妙，使用了 cnt 数组来记录变化量个数，之后可以通过遍历这个 cnt 数组来确定最小操作次数。
  相比之下我的解法就很麻烦，把每种情况逐一考虑，这样子很容易忽视某种情况。
• 解法二使用了很多 C++ 的函数，比如 accumulate ，可以直接求总和，其中第三个形参是累加的初值。
• 解法二直接使用了 swap 函数交换两个数组，确保数组 nums1 的总和一定小于 nums2。省略了 if 的比较。而我的方法则是确定总和较小和较大的数组，传入 count函数中。

时间复杂度：O（m+n），其中 m 和 n 分别是两个数组的长度；
空间复杂度：O（C），这里 C 为 6 ，即数组 cnt 所使用的空间大小。

class Solution {
public:int minOperations(vector& nums1, vector& nums2) {if(6 * nums1.size() < nums2.size() || 6 * nums2.size() < nums1.size())  return -1;int diff = accumulate(nums2.begin(), nums2.end(), 0) - accumulate(nums1.begin(), nums1.end(), 0);if(diff < 0){ // nums1总和较大diff = abs(diff);swap(nums1, nums2); // 统一使nums1的数变大，nums2的数变小}vector cnt(6); // 统计每个数的变化量for(int x : nums1) ++cnt[6 - x];for(int x : nums2) ++cnt[x - 1];for(int i = 5, ans = 0;; --i){ // 从大到小枚举最大变化量 5 4 3 2 1if(i * cnt[i] >= diff) // 可以让 d 变为 0return ans + (diff + i - 1) / i;ans += cnt[i]; // 需要所有最大变化量为i的数diff -= i * cnt[i];}}
};

参考资料：

1. 没想明白？一个动画秒懂！（Python/Java/C++/Go）