LeetCode刷题笔记-2333-最小差值平方和 2026.10.10 算法蒟蒻的成长记录，LeetCode 字数：3.7k 阅读时间：17 分钟 已发布 6 天

题目信息

• 平台：LeetCode
• 题目：2333. Minimum Sum Square Difference
• 难度：Medium
• 题目链接：最小差值平方和

---

题目描述

给定两个长度为 的非负整数数组 nums1 和 nums2。你可以对 nums1 中的任意元素执行恰好 次操作（加 或减 ），对 nums2 中的任意元素执行恰好 次操作。

请你返回让 尽可能小的结果。

注意：操作后的元素可以是负数，不要求保持非负。

数据范围：，，。

---

初步思路

这道题是一道非常经典的贪心问题，可以从数学性质转化、核心贪心策略以及两种具体实现来拆解。

1. 操作等价性：合并 和

设 ，我们要最小化的是 。

• 对 nums1[i] 加 ，与对 nums2[i] 减 的效果完全一样，都是让两者的差值绝对值向 靠近 ；
• 对 nums1[i] 减 ，与对 nums2[i] 加 ，同样都能让差值远离 ，只会让答案变大；
• 因此**存在一个最优解，其中每次操作都用来让某个 减小 **，没有任何一次操作是在把某个数推得更远；
• 所以两个数组的操作预算可以完全等价地互换，** 与 可以直接合并为一个总操作次数 **。

为什么「恰好 次」不影响这个结论？
如果所有差值都已削到 （即 ），剩下的操作可以全部浪费在同一个元素上反复加 再减 ，答案不变。
所以我们只需关心至多使用 次有效操作即可，这也是后面代码里那句 if (sum_d <= k) return 0; 的由来。

这一步转化把「两个数组分别操作」简化成了「单个差值数组削峰」，是后面所有算法的基础。

2. 贪心策略：为什么优先减去最大的差值？

观察数值从 变成 时，平方差的变化量：

显然，** 越大， 就越大，收益也就越高。为了让总平方和下降得最多，我们每一次操作都应该贪心地减小当前最大的 **。

换句话说，我们的目标是：「削峰填谷」——把数组中的所有大数尽量削平，让它们变得尽可能小且均匀。

如果所有差值之和 ，我们可以把所有差值全变成 ，答案直接为 。

---

解法选择

针对这种「把所有数削平」的问题，通常有两种最优解。

解法 1：计数/桶模拟（最推荐，简单且快）

注意到题目数据范围 ，因此差值 的最大值不会超过 。

• 用一个频数数组 cnt[v] 记录差值为 的元素个数；
• 从最大值 开始从大到小往下模拟：
  • 如果剩余的 ：说明能把这 个数全部削低 （变成 ），于是 ，；
  • 如果 ：说明只能削低其中的 个数， 个数变成 ，剩下 个保持为 ，此时 用完，退出循环。

时间复杂度：，一次线性遍历，效率极高。

解法 2：二分答案（通用解法，面试官最喜欢的扩展）

如果题目把数据范围扩大到 ，桶数组就开不下了，必须用二分查找：

• 二分最终所有差值的**「上限」 **（即所有大于 的数都被削到了 ）；
• check(T)：计算把所有大于 的差值削到 需要多少次操作 。若操作数 ，说明上限 可以达到（甚至可能更小）；
• 找到最小可达的 之后，如果还有剩余的 ，由于 是下限，我们只能把一部分刚好等于 的数进一步减成 。

时间复杂度：。

还有第三种思路：大顶堆批量削减（本题不推荐）

用大顶堆维护差值、每次取出最大值减 ，是最直观的想法。但直接这么写必然超时： 最大可达 ，逐次操作是 ，跑不完。

可行的改法是按层批量削减——把堆里的元素组织成 (差值, 出现次数)，整层一起下沉、合并同值条目，从而避免逐次操作。

不过这条路有两个限制：

• 复杂度并不占优。设不同差值的个数为 ，其复杂度约为 ，相比桶计数法的 和二分答案法的 都没有优势，纯粹是多绕了一层；
• 实现易错。批量合并时若把已弹出的条目丢弃，会导致元素凭空消失、 的消耗算错，是这道题最容易写错的地方。

因此本文只给出前两种实现。面试时如果被问到「还有别的思路吗」，可以提堆的批量削减思路并说明上述限制——它证明的是你知道怎么分析取舍，而不是必须写出代码。

---

算法分析

• 核心思想：把两个数组的操作等价合并为对差值数组的「削峰」，优先减小最大的差值
• 技巧要点：用频次数组 模拟削峰；或二分出最大差值上限，再把剩余操作分配给等于上限的元素
• 时间复杂度：桶计数法 ；二分答案法
• 空间复杂度：桶计数法 ；二分答案法

---

代码实现

解法一：桶计数法

cpppythonjavagorust

class Solution {
public:
    long long minSumSquareDiff(vector<int>& nums1, vector<int>& nums2, int k1, int k2) {
        int n = nums1.size();
        long long k = (long long)k1 + k2;

        const int M = 100000;
        vector<int> cnt(M + 1, 0);
        int max_d = 0;
        long long sum_d = 0;

        for (int i = 0; i < n; ++i) {
            int d = abs(nums1[i] - nums2[i]);
            cnt[d]++;
            max_d = max(max_d, d);
            sum_d += d;
        }

        // 操作数足以把所有差值清零
        if (sum_d <= k) return 0;

        // 从大到小削峰
        for (int v = max_d; v > 0; --v) {
            if (cnt[v] == 0) continue;

            if (k >= cnt[v]) {
                // 这一层的全部削到 v-1
                k -= cnt[v];
                cnt[v - 1] += cnt[v];
                cnt[v] = 0;
            } else {
                // 只削 k 个就停
                cnt[v] -= k;
                cnt[v - 1] += k;
                k = 0;
                break;
            }
        }

        long long ans = 0;
        for (int v = 1; v <= max_d; ++v) {
            if (cnt[v] > 0) ans += (long long)cnt[v] * v * v;
        }
        return ans;
    }
};

解法二：二分答案法

下面这组是通用版实现，数据范围很大时桶数组开不下，就用二分。

cpppythonjavagorust

class Solution {
public:
    long long minSumSquareDiff(vector<int>& nums1, vector<int>& nums2, int k1, int k2) {
        int n = nums1.size();
        long long k = (long long)k1 + k2;

        vector<int> d(n);
        int max_val = 0;
        long long total = 0;

        for (int i = 0; i < n; ++i) {
            d[i] = abs(nums1[i] - nums2[i]);
            max_val = max(max_val, d[i]);
            total += d[i];
        }

        if (total <= k) return 0;

        // 判断能否把所有大于 mid 的差值削到 mid
        auto check = [&](int mid) -> bool {
            long long need = 0;
            for (int x : d) {
                if (x > mid) need += x - mid;
            }
            return need <= k;
        };

        // 二分最小可达上限
        int left = 0, right = max_val;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (check(mid)) right = mid;
            else left = mid + 1;
        }

        int limit = left;

        // 先削到 limit，再用剩余操作把等于 limit 的继续削低
        for (int x : d) {
            if (x > limit) k -= (x - limit);
        }

        long long ans = 0;
        for (int x : d) {
            int cur = min(x, limit);
            if (cur == limit && k > 0 && cur > 0) {
                cur--;
                k--;
            }
            ans += 1LL * cur * cur;
        }

        return ans;
    }
};

---

测试用例

输入	输出	说明
nums1 = [1,2,3,4], nums2 = [2,10,20,19], k1 = 0, k2 = 0	579	官方样例 1： 无法操作，，平方和
nums1 = [1,4,10,12], nums2 = [5,8,6,9], k1 = 1, k2 = 1	43	官方样例 2：， 分别削掉 中最大的两个 ，得 ，平方和
nums1 = [5,2], nums2 = [4,3], k1 = 3, k2 = 1	0	边界：，，全部削平
nums1 = [1], nums2 = [6], k1 = 5, k2 = 1	0	边界：，直接清零

两种解法、五种语言的实现均已在本地对上述用例验证通过，输出完全一致。

---

容易踩坑的细节

1. 整数溢出
   • 最大为 ，虽然还没超过 int 上限（），但已经非常接近。不同语言的 int 宽度并不统一，用 64 位类型存 更稳妥；
   • 真正会溢出的是平方和： 最大可达 ，远超 int 上限，必须使用 64 位整数；
   • C++ 的乘运算是左结合的，写 cnt[v] * v * v 会先算 cnt[v] * v，这一步就已经溢出了。要写 (long long)cnt[v] * v * v，让第一个参与乘法的数就是 64 位类型。
2. 剩余操作的处理
   • 在二分求出上限 limit 后，剩下的 只能分给恰好等于 limit 的元素使其变成 limit - 1，不能给已经小于 limit 的元素；
   • 同时要注意 limit 为 时不能再往下削，否则差值会变成负数。
3. 桶计数法的边界
   • cnt 数组要开到 （差值最大就是 ），否则 cnt[v-1] += cnt[v] 在 时会越界；
   • 削峰循环条件是 v > 0， 的元素无法再削减。

---

总结与反思

1. 先做等价转化，再谈算法。把「对两个数组分别加减 、 次」合并成「对差值数组操作 次」，是本题最关键的一步转化，跳过它容易陷入错误的分类讨论。
2. 导出了贪心。差值从 降一带来的收益随 线性增长，因此「优先削最大的」永远最优——这是整个思路的理论支点。
3. 数据范围决定选型。 时桶计数法 明显更优；一旦到 量级，桶开不下，才需要二分答案的 。面试时把两者都讲出来更能体现对「复杂度依赖值域」的理解。
4. 易错点：整数溢出。平方和 可达 ，远超 int 上限，累加必须用 64 位类型；同时注意 C++ 乘法的左结合陷阱。