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

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

class Solution {
public:
    int count(vector<int>& nums_min, vector<int>& 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<int>());
        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 || p<len1 && q<len2 && nums_min[p]==6 && nums_max[q]>1){
            while(q < len2 && diff>0){
                b = nums_max[q] - 1;
                diff -= b;
                q ++;
                cnt ++;
            }
        }
        
        // 遍历nums_min
        // 情况1:要么是nums_max全为1，要么是已经遍历到最后一个值
        if(q == len2 ||p<len1 && q<len2 && nums_max[q]==1 && nums_min[p]<6){
            while(p<len1 && diff>0){
                a = 6 - nums_min[p];
                diff -= a;
                p ++;
                cnt ++;
            }
        }    
        if(diff>0) cnt = -1;
        return cnt;
    }
    int minOperations(vector<int>& nums1, vector<int>& 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=0
        if(sum1 < sum2) cnt = count(nums1, nums2, diff);
        else cnt = count(nums2, nums1, diff);

        return cnt;
    }
};

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

class Solution {
public:
    int minOperations(vector<int>& nums1, vector<int>& 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<int> 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 1
            if(i * cnt[i] >= diff) // 可以让 d 变为 0
                return ans + (diff + i - 1) / i;
            ans += cnt[i]; // 需要所有最大变化量为i的数
            diff -= i * cnt[i];
        }
    }
};

参考资料：

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