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

## 问题描述
[1775.通过最少操作次数使数组的和相等](https://leetcode.cn/problems/equal-sum-arrays-with-minimum-number-of-operations/)

## 解题思路
### 哈希+贪心
本题总体思路为哈希+贪心，用两个数组`mp1`，`mp2`记录`nums1`，`nums2`中每个数各出现了多少次;

假设`nums1`的和`sum1`减去`nums2`的和`sum2`的结果为`diff`，这里假设`diff > 0`，为了抹平两个数组的和的差距，应该每次减去两个数组中，变化数字引起的数值变化的最大值，并且将变化的数字的计数值减一;

`nums1`的和小于`nums2`的和的情况类似。

### 优化
首先假设`sum1 < sum2`，否则我们交换`nums1`和`nums2`并交换`sum1`和`sum2`即可，接下来，必定是`nums1`缩小，`nums2`增大，对应`diff = sum2 - sum1`缩小，`diff`可以减少`1,2,3,4,5`各若干次，取决于`nums1`和`nums2`中原先各个数的数量，用一个哈希表来记录，最后我们从大到小遍历`i = 5, 4, 3, 2, 1`.


## 代码
### hash + greedy algorithm
```cpp
class Solution {
public:
    int find_min(vector<int> &v) {
        for (int i = 1; i < v.size(); i++) {
            if (v[i] != 0)
                return i;
        }
        return 6;
    }
    int find_max(vector<int> &v) {
        for (int i = v.size() - 1; i >= 1; i--) {
            if (v[i] != 0)
                return i;
        }
        return 1;
    }
    int minOperations(vector<int>& nums1, vector<int>& nums2) {
        int sum1 = 0, sum2 = 0;
        vector<int> mp1(7, 0);
        vector<int> mp2(7, 0);
        if (nums1.size() > 6 * nums2.size() || 6 * nums1.size() < nums2.size())
            return -1;
        for (int i = 0; i < nums1.size(); i++) {
            mp1[nums1[i]]++;
            sum1 += nums1[i];
        }
        for (int i = 0; i < nums2.size(); i++) {
            mp2[nums2[i]]++;
            sum2 += nums2[i];
        }
        int diff = sum1 - sum2;
        int cnt = 0;
        if (diff == 0)
            return cnt;
        else if (diff > 0) {
            // 对nums1, 移动一次最多减少 find_max(mp1) - 1;
            // 对nums2, 移动一次最多增加 6 - find_min(mp2);
            while (diff > 0) {
                cnt++;
                int minus1 = find_max(mp1) - 1;
                int plus2 = 6 - find_min(mp2);
                if (minus1 >= plus2) {
                    diff -= minus1;
                    mp1[find_max(mp1)]--;
                } else {
                    diff -= 6 - find_min(mp2);
                    mp2[find_min(mp2)]--;
                }
            }
            return cnt;
        } else {
            // 对nums1, 移动一次最多增加 6 - find_min(mp1);
            // 对nums2, 移动一次最多减少 find_max(mp2) - 1;
            while (diff < 0) {
                cnt++;
                int minus2 = find_max(mp2) - 1;
                int plus1 = 6 - find_min(mp1);
                if (minus2 >= plus1) {
                    diff += minus2;
                    mp2[find_max(mp2)]--;
                } else {
                    diff += plus1;
                    mp1[find_min(mp1)]--;
                }
            }
            return cnt;                  
        }

    }
};
```

### better code
```cpp
class Solution {
  public:
    int minOperations(vector<int> &nums1, vector<int> &nums2) {
        // 先判断不可能相等的情况
        if (nums1.size() > 6 * nums2.size() || nums2.size() > 6 * nums1.size()) {
            return -1;
        }
        // 两个数组的和
        int sum1 = 0, sum2 = 0;
        unordered_map<int, int> mp1;
        for (int &num : nums1) {
            sum1 += num;
        }
        for (int &num : nums2) {
            sum2 += num;
        }
        if (sum1 == sum2) {
            return 0;
        }
        if (sum1 > sum2) {
            vector<int> tmp = nums1;
            int tmp_sum = sum1;
            nums1 = nums2;
            sum1 = sum2;
            nums2 = tmp;
            sum2 = tmp_sum;
        }
        int cnt = 0;
        int diff = sum2 - sum1;
        for (int num : nums1) {
            ++mp1[6 - num];
        }
        for (int num : nums2) {
            ++mp1[num - 1];
        }
        for (int i = 5;; i--) {
            if (diff <= i * mp1[i]) {
                return cnt + (diff + i - 1) / i;
            }
            cnt += mp1[i];
            diff -= i * mp1[i];
        }
        return cnt;
    }
};