企业官网建设流程全解析

【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 11，想要使平方和最小，应该减小哪个数？

   应该减小最大的那个数。

   假设a > b a\gt ba>b，那么( a − 1 ) 2 + b 2 = a 2 + b 2 + 1 − 2 a (a-1)^2 + b^2 = a^2 + b^2 + 1 - 2a(a−1)2+b2=a2+b2+1−2a，a 2 + ( b − 1 ) 2 = a 2 + b 2 + 1 − 2 b a^2 + (b-1)^2 = a^2 + b^2 + 1 - 2ba2+(b−1)2=a2+b2+1−2b，因为a > b a\gt ba>b，所以− 2 a < − 2 b -2a \lt -2b−2a<−2b，所以减小a aa更优。

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 00），最终的diffs数组中每个元素的平方和即为所求。

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

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

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

2. 如果剩余的k不够多（k < ( d i f f s [ i ] − d i f f s [ i + 1 ] ) ∗ ( i + 1 ) k < (diffs[i] - diffs[i + 1]) * (i + 1)k<(diffs[i]−diffs[i+1])∗(i+1)），那么只能把k m o d ( i + 1 ) k \mod (i + 1)kmod(i+1)个元素减少⌊ k i + 1 ⌋ + 1 \lfloor\frac{k}{i+1}\rfloor+1⌊i+1k​⌋+1以及把i + 1 − ( k m o d ( i + 1 ) ) i+1-(k \mod (i + 1))i+1−(kmod(i+1))个元素减少⌊ k i + 1 ⌋ \lfloor\frac{k}{i+1}\rfloor⌊i+1k​⌋。

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

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

时空复杂度

• 时间复杂度O ( N 2 ) O(N^2)O(N2)
• 空间复杂度O ( N log ⁡ N ) O(N\log N)O(NlogN)

AC代码

C++

/* * @LastEditTime: 2026-10-12 19:25:34 */typedeflonglongll;classSolution{public:llminSumSquareDiff(vector<int>&nums1,vector<int>&nums2,intk1,intk2){intn=nums1.size();vector<int>diffs(nums1.size()+1);// 末尾多一个哨兵for(inti=0;i<n;i++){diffs[i]=abs(nums1[i]-nums2[i]);}ranges::sort(diffs,greater<int>());intk=k1+k2;for(inti=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];}returnans;}return0;}};

End

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

千篇源码题解已开源