2333.最小差值平方和：排序 + 数学计算（不用二分）

【LetMeFly】2333.最小差值平方和：排序 + 数学计算（不用二分）

力扣题目链接：https://leetcode.cn/problems/minimum-sum-of-squared-difference/

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，长度为 n 。

数组 nums1 和 nums2 的 差值平方和 定义为所有满足 0 <= i < n 的 (nums1[i] - nums2[i])2 之和。

同时给你两个正整数 k1 和 k2 。你可以将 nums1 中的任意元素 +1 或者 -1 至多 k1 次。类似的，你可以将 nums2 中的任意元素 +1 或者 -1 至多 k2 次。

请你返回修改数组 nums1 至多 k1 次且修改数组 nums2 至多 k2 次后的最小 差值平方和 。

注意：你可以将数组中的元素变成 负 整数。

 

示例 1：

输入：nums1 = [1,2,3,4], nums2 = [2,10,20,19], k1 = 0, k2 = 0
输出：579
解释：nums1 和 nums2 中的元素不能修改，因为 k1 = 0 和 k2 = 0 。
差值平方和为：(1 - 2)2 + (2 - 10)2 + (3 - 20)2 + (4 - 19)2 = 579 。

示例 2：

输入：nums1 = [1,4,10,12], nums2 = [5,8,6,9], k1 = 1, k2 = 1
输出：43
解释：一种得到最小差值平方和的方式为：
- 将 nums1[0] 增加一次。
- 将 nums2[2] 增加一次。
最小差值平方和为：
(2 - 5)2 + (4 - 8)2 + (10 - 7)2 + (12 - 9)2 = 43 。
注意，也有其他方式可以得到最小差值平方和，但没有得到比 43 更小答案的方案。

 

提示：

• n == nums1.length == nums2.length
• 1 <= n <= 105
• 0 <= nums1[i], nums2[i] <= 105
• 0 <= k1, k2 <= 109

解题方法：排序 + 数学计算

已知两个前提：

1. 假设有多个正整数只能选其中一个减少$1$，想要使平方和最小，应该减小哪个数？

   应该减小最大的那个数。

   假设$a\gt b$，那么$(a-1)^2 + b^2 = a^2 + b^2 + 1 - 2a$，$a^2 + (b-1)^2 = a^2 + b^2 + 1 - 2b$，因为$a\gt b$，所以$-2a \lt -2b$，所以减小$a$更优。

2. 对nums1的操作，总有办法对nums2的等价操作。

   所以对nums1进行最多k1次操作、对nums2进行最多k2次操作，相当于最多进行k1 + k2次加减一操作。

   因为如果想要对nums1[i] + 1然后和nums2[i]求差值平方但是k1已经用完了的话，直接让nums2[i] - 1然后和nums1[i]求差值平方是等价的。

所以，我们直接求出两个数组一一对应两元素的差值数组diffs，其中diffs[i] = abs(nums1[i] - nums2[i])，每次减少diffs中最大的元素共计操作至多k1 + k2次（最多减少到$0$），最终的diffs数组中每个元素的平方和即为所求。

但是，k1 + k2可能是$10^9$级别的，所以我们不能真的一个一个地去试，而是一次减多个元素，每个元素减好几。

具体而言，对diffs数组从大到小排序。假设当前元素是diffs[i]（下一个元素是diffs[i + 1]），那么我们可以尽量把从diffs[0]到diffs[i]的所有元素都减小到diffs[i + 1]（共计需要减少$(diffs[i] - diffs[i + 1]) \times (i + 1)$次）：

1. 如果剩余的k足够多（$k\geq (diffs[i] - diffs[i + 1]) * (i + 1)$），那么就把diffs[0]到diffs[i]都减小到diffs[i + 1]（消耗$(diffs[i] - diffs[i + 1]) \times (i + 1)$次操作），然后继续处理下一个元素。

2. 如果剩余的k不够多（$k < (diffs[i] - diffs[i + 1]) * (i + 1)$），那么只能把$k \mod (i + 1)$个元素减少$\lfloor\frac{k}{i+1}\rfloor+1$以及把$i+1-(k \mod (i + 1))$个元素减少$\lfloor\frac{k}{i+1}\rfloor$。

   到此为止，k已经消耗完毕，就不需要再继续遍历了，开始计算。$0$到$i$的diff中有$k \mod (i + 1)$个diff是$diffs[i] - \lfloor\frac{k}{i+1}\rfloor - 1$，有$i + 1 - (k \mod (i + 1))$个diff是$diffs[i] - \lfloor\frac{k}{i+1}\rfloor$，剩余的diffs[i + 1]到diffs[n - 1]是原值不变。

特别的，我们可以向diffs数组后面插入一个哨兵元素$0$。如果循环结束了，说明每个diff都减少到了$0$，直接返回$0$。

时空复杂度

• 时间复杂度$O(n\log n)$，时间复杂度主要来自排序
• 空间复杂度$O(n)$，如果原地修改其中一个参数数组可以将空间复杂度降低到$O(\log n)$

AC代码

C++

/*
 * @LastEditTime: 2026-10-12 19:25:34
 */
typedef long long ll;
class Solution {
public:
    ll minSumSquareDiff(vector<int>& nums1, vector<int>& nums2, int k1, int k2) {
        int n = nums1.size();
        vector<int> diffs(nums1.size() + 1);  // 末尾多一个哨兵
        for (int i = 0; i < n; i++) {
            diffs[i] = abs(nums1[i] - nums2[i]);
        }
        ranges::sort(diffs, greater<int>());

        int k = k1 + k2;
        for (int i = 0; i < n; i++) {
            ll per_diff = diffs[i] - diffs[i + 1];
            ll all_need = per_diff * (i + 1);
            if (k >= all_need) {
                k -= all_need;
                continue;
            }
            /*
                不够全部减小到目标值了，看看能减小到多少。
                假设k = 3, i = 1, all_need = 5
                k // 2 = 1，2个数每个减少1
                k % 2 = 1，其中1个数再减少一
            */
            ll all_sub = k / (i + 1);
            ll more_sub_1 = k % (i + 1);
            ll not_more_sub_1 = i + 1 - more_sub_1;
            diffs[i] -= all_sub;
            ll ans = not_more_sub_1 * diffs[i] * diffs[i];
            ans += more_sub_1 * (diffs[i] - 1) * (diffs[i] - 1);
            for (i++; i < n; i++) {
                ans += (ll) diffs[i] * diffs[i];
            }
            return ans;
        }
        return 0;
    }
};

End

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源