LeetCode 题解工作台
最小差值平方和
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，长度为 n 。 数组 nums1 和 nums2 的 差值平方和 定义为所有满足 0 的 (nums1[i] - nums2[i]) 2 之和。 同时给你两个正整数 k1 和 k2 。你可以将 nums1 中的任意元素 +1 或者 -…
5
题型
4
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
class Solution: def minSumSquareDiff(
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你两个下标从 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.length1 <= n <= 1050 <= nums1[i], nums2[i] <= 1050 <= k1, k2 <= 109
解题思路
方法一：二分查找
class Solution:
def minSumSquareDiff(
self, nums1: List[int], nums2: List[int], k1: int, k2: int
) -> int:
d = [abs(a - b) for a, b in zip(nums1, nums2)]
k = k1 + k2
if sum(d) <= k:
return 0
left, right = 0, max(d)
while left < right:
mid = (left + right) >> 1
if sum(max(v - mid, 0) for v in d) <= k:
right = mid
else:
left = mid + 1
for i, v in enumerate(d):
d[i] = min(left, v)
k -= max(0, v - left)
for i, v in enumerate(d):
if k == 0:
break
if v == left:
k -= 1
d[i] -= 1
return sum(v * v for v in d)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n log D) where D is the maximum difference between nums1 and nums2, due to binary search combined with heap operations. Space complexity is O(n) to store differences and the max-heap. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Focus on reducing the largest differences first.
- question_mark
Consider k1 and k2 as interchangeable resources.
- question_mark
Binary search is intended over the valid squared sum range.
常见陷阱
外企场景- error
Failing to combine k1 and k2 for total modifications, treating them separately.
- error
Attempting to greedily adjust without tracking the largest difference first.
- error
Miscomputing the squared sum after adjustments, missing zero-floor constraints.
进阶变体
外企场景- arrow_right_alt
Allow only increasing elements in nums1 and decreasing in nums2.
- arrow_right_alt
Limit modifications to specific indices rather than all elements.
- arrow_right_alt
Change the cost function to weighted squared differences or absolute differences.