# 1775. Equal Sum Arrays With Minimum Number of Operations
###### tags: `Leetcode` `Microsoft` `Medium` `Two Pointers`
Link: https://leetcode.com/problems/equal-sum-arrays-with-minimum-number-of-operations/
## 思路
参考[这里](https://leetcode.com/problems/equal-sum-arrays-with-minimum-number-of-operations/discuss/1085786/JavaPython-3-2-Greedy-codes%3A-sort-and-count-w-brief-explanation-and-analysis.)
### 思路一 Sort and Two Pointers
最直觉的办法
1. In order to make the two sum's equal, we need either to increase to 6 the numbers in the smaller sum array or decrease to 1 the numbers in the bigger sum array;
2. Since we want to complete the task with minimum operations, it is optimal to choose the greater between the increase and decrease. Hence this is a greedy algorithm.

所以我们将两个array排序 小的那个从左到右遍历 大的从右到左遍历 每次比较到底是增加左边的还是减少右边的 直到原本小的sum比原本大的sum要大
### 思路二
用cnt计算sum1的上升空间
[6-num]是在sum小的array里面的每个数字的上升空间
[num-1]是在sum大的array里面的每个数字的下降空间
和在一起 就是sum小的array的所有上升空间
只要从右到左遍历一遍 就可以找到答案
## Code
### 思路一 Sort and Two Pointers

class Solution {
    public int minOperations(int[] nums1, int[] nums2) {
        if(nums1.length*6<nums2.length || nums1.length>nums2.length*6){
            return -1;
        }
        int sum1 = 0, sum2 = 0;
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        for(int num:nums1){
            sum1 += num;
        } 
        for(int num:nums2){
            sum2 += num;
        }
        if(sum1>sum2) return minOperations(nums2, nums1);
        if(sum1==sum2) return 0;
        int p1 = 0, p2 = nums2.length-1;
        int ans = 0;
        while(sum1<sum2){
            if(p2<0 || (p1<nums1.length && 6-nums1[p1]>nums2[p2]-1)){
                sum1 += 6-nums1[p1];
                p1++;
            }
            else{
                sum1 += nums2[p2]-1;
                p2--;
            }
            ans++;
        }
        return ans;
    }
}

## 思路二 Count the increases and decreases

class Solution {
    public int minOperations(int[] nums1, int[] nums2) {
        if(nums1.length*6<nums2.length || nums1.length>nums2.length*6){
            return -1;
        }
        int sum1 = 0, sum2 = 0;
        int[] cnt = new int[7];
        for(int num:nums1){
            sum1 += num;
            cnt[6-num]++;
        } 
        for(int num:nums2){
            sum2 += num;
            cnt[num-1]++;
        }
        if(sum1>sum2) return minOperations(nums2, nums1);
        if(sum1==sum2) return 0;
        int ans = 0;
        int i = 5;
        while(sum1<sum2 && i>0){
            if(cnt[i]==0){
                i--;
            }
            else{
                sum1 += i;
                ans++;
                cnt[i]--;
            }
        }
        return ans;
    }
}