LeetCode 1674. 使数组互补的最少操作次数
目录
题目描述
题意分析
给定长度为偶数
n的数组nums和上界limit。一次操作可以把任意一个元素替换成1到limit之间的任意整数。数组称为「互补」，当且仅当所有对称位置的和都相等，即nums[i] + nums[n-1-i]对所有i是同一个值。求达成互补所需的最少操作次数。第一层转化：
n是偶数，所以数组被完整拆成n/2对，每对由nums[i]和nums[n-1-i]组成，各对之间互不影响。互补要求它们统一到同一个目标和x。于是问题变成：枚举目标和
x，把每一对调整到x的代价加起来，取全局最小。x的取值范围是[2, 2*limit]——两个元素最小都是 1，最大都是limit。第二层转化在于代价函数。对一对
(a, b)，记lo = min(a,b)、hi = max(a,b)，把它调成和为x的代价只有 0、1、2 三种，而且每种代价对应的x是一段连续区间。既然是「对一批区间做加法，最后查每个位置的总值」，那就是差分数组的标准场景。边界：如果原数组已经互补（如
[1,2,1,2]），答案是 0；直接对每个x重新遍历所有对是 $O(n \cdot limit)$，在n和limit都到 $10^5$ 时会超时，这正是需要差分的原因。
解法：枚举目标和 + 差分数组统计代价
核心思路
先把单对的代价函数推清楚。对一对
(lo, hi)（已保证lo <= hi，且两者都在[1, limit]内）：
- 改 0 个数：只能得到原来的和，即
x = lo + hi，代价 0。- 改 1 个数：保留一个、把另一个换成
[1, limit]中任意值。保留lo可得到的和是[lo+1, lo+limit]，保留hi可得到[hi+1, hi+limit]。因为lo >= 1且hi <= limit，有lo + limit >= 1 + hi = hi + 1，两段相接或重叠，并起来是一整段连续区间[lo+1, hi+limit]，代价 1。- 改 2 个数：两个都换，任意
x ∈ [2, 2*limit]都能达到，代价 2。这三档是包含关系，取最小即得：
x = lo+hi时代价 0；x落在[lo+1, hi+limit]内（且不等于lo+hi）时代价 1；其余情况代价 2。直接对每个
x累加所有对的代价是 $O(n \cdot limit)$。改用差分：把「代价 2 铺满全区间，再在[lo+1, hi+limit]上减 1，再在单点lo+hi上再减 1」这三次区间加记录成差分数组上的常数次修改。每一对只需 6 次数组写入，与limit无关。全部对处理完后对差分数组求前缀和，
x位置的前缀和就是「把所有对都调成x」的总代价，扫一遍取最小值即为答案。「代价 2 铺满 + 逐层减 1」这个写法的好处是不必显式处理代价 2 的那两段零散区间（
[2, lo]和[hi+limit+1, 2*limit]），避免了边界拼接出错。
解题步骤
- 开差分数组：长度取
2*limit + 2，让下标最大能写到2*limit + 1（区间右端点加一的位置）。有效的x只在[2, 2*limit]，下标 0 和 1 永远不会被写。- 遍历前半段：
i从 0 到n/2 - 1，取出nums[i]与nums[n-1-i]，令lo为较小者、hi为较大者。必须先取 min/max，后面所有区间端点的推导都建立在lo <= hi之上。- 铺代价 2：
diff[2] += 2、diff[2*limit+1] -= 2，表示默认这一对要改两个数。- 减出代价 1 区间：
diff[lo+1] -= 1、diff[hi+limit+1] += 1，把[lo+1, hi+limit]上的代价从 2 降到 1。- 减出代价 0 单点：
diff[lo+hi] -= 1、diff[lo+hi+1] += 1，把x = lo+hi再降到 0。注意lo+hi一定落在上一步的区间内，所以是「再减 1」而不是「设为 0」。- 前缀和取最小：
x从 2 扫到2*limit，滚动累加差分值，同时记录最小值。累加的起点是 2，不需要真的建出前缀和数组。- 返回最小值。
以
nums = [1,2,4,3]、limit = 4走一遍。两对分别是(nums[0], nums[3]) = (1,3)与(nums[1], nums[2]) = (2,4)，x的范围是[2, 8]。第一对
lo=1, hi=3：铺满diff[2] += 2；代价 1 区间是[2, 7]，故diff[2] -= 1、diff[8] += 1；代价 0 单点是x=4，故diff[4] -= 1、diff[5] += 1。第二对lo=2, hi=4：diff[2] += 2；代价 1 区间[3, 8]，diff[3] -= 1、diff[9] += 1；代价 0 单点x=6，diff[6] -= 1、diff[7] += 1。求前缀和得到各目标和的总代价：
x=2是 3，x=3是 2，x=4是 1，x=5是 2，x=6是 1，x=7是 2，x=8是 3。最小值 1，与期望输出一致。可以人工验证x=4：第一对1+3=4本来就满足，代价 0；第二对(2,4)把 4 改成 2 即可，代价 1，合计 1。再看
nums = [1,2,1,2]、limit = 2：两对都是(1,2)，代价 0 单点都在x=3，前缀和在x=3处为 0，答案 0——原数组已经互补，一次操作都不用。
代码实现
class Solution {
public int minMoves(int[] nums, int limit) {
int n = nums.length;
// diff 记录目标和 x 上的代价增量，x 的有效范围是 [2, 2*limit]。
int[] diff = new int[2 * limit + 2];
for (int i = 0; i < n / 2; i++) {
int lo = Math.min(nums[i], nums[n - 1 - i]);
int hi = Math.max(nums[i], nums[n - 1 - i]);
// 默认这一对要改两个数。
diff[2] += 2;
diff[2 * limit + 1] -= 2;
// 落在 [lo+1, hi+limit] 内只需改一个数。
diff[lo + 1] -= 1;
diff[hi + limit + 1] += 1;
// 恰好等于原和时一个都不用改。
diff[lo + hi] -= 1;
diff[lo + hi + 1] += 1;
}
int ans = n;
int cur = 0;
for (int x = 2; x <= 2 * limit; x++) {
cur += diff[x];
ans = Math.min(ans, cur);
}
return ans;
}
}
func minMoves(nums []int, limit int) int {
n := len(nums)
// diff 记录目标和 x 上的代价增量，x 的有效范围是 [2, 2*limit]。
diff := make([]int, 2*limit+2)
for i := 0; i < n/2; i++ {
lo, hi := nums[i], nums[n-1-i]
if lo > hi {
lo, hi = hi, lo
}
// 默认这一对要改两个数。
diff[2] += 2
diff[2*limit+1] -= 2
// 落在 [lo+1, hi+limit] 内只需改一个数。
diff[lo+1]--
diff[hi+limit+1]++
// 恰好等于原和时一个都不用改。
diff[lo+hi]--
diff[lo+hi+1]++
}
ans, cur := n, 0
for x := 2; x <= 2*limit; x++ {
cur += diff[x]
if cur < ans {
ans = cur
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n + limit)$。每一对只做常数次差分写入，共 $O(n)$；最后扫一遍
[2, 2*limit]求前缀和取最小，共 $O(limit)$。相比「对每个x重算所有对」的 $O(n \cdot limit)$，差分把二者从相乘变成相加。- 空间复杂度：$O(limit)$，只需一个长度为
2*limit + 2的差分数组，不随n增长。
关键点总结
- 偶数长度保证了数组被完整拆成互不影响的对，「全局统一目标」因此可以拆成「每对独立计代价再求和」。
- 单对代价只有 0/1/2 三档，且每档对应
x上的一段连续区间——这是能用差分的根本原因；若代价对x不分段连续，差分就无从下手。- 代价 1 的两段区间之所以能合并成
[lo+1, hi+limit]，靠的是lo >= 1与hi <= limit推出的lo + limit >= hi + 1，不是巧合。- 「铺满最大代价再逐层减 1」比「分段写入 0/1/2」更不容易错，因为它把零散的边界区间转成了嵌套的区间减法。
- 判断该用差分而非直接枚举，看的是「区间修改次数 × 区间长度」是否超出预算，而不是题面有没有出现「区间」二字。
易错点总结
- 忘记先取 min/max：
[lo+1, hi+limit]这个区间的推导要求lo <= hi，直接用nums[i]和nums[n-1-i]的原始顺序会算出错误区间。- 差分数组开小：右端点加一的位置最大是
2*limit + 1，长度必须至少2*limit + 2，否则diff[hi+limit+1]越界。- 代价 0 写成「设为 0」：
x = lo+hi已经在代价 1 区间内，只能再减 1；直接赋 0 会破坏差分的累加语义。- 前缀和从
x = 0或x = 1开始：这两个下标不是合法目标和，把它们计入会得到偏小的假答案。x必须从 2 起。- 答案初值取 0：应取一个安全上界。每对代价至多 2、共
n/2对，总代价不超过n，所以用n作初值最稳妥。- 对每个
x重新遍历数组：逻辑正确但 $O(n \cdot limit)$，在n与limit同为 $10^5$ 量级时必然超时。- 误以为要让所有元素相等：题目只要求对称位置的和相等，不是元素相等。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 370. 区间加法 | 中等 | 差分数组的裸题，只有区间加与最终还原两步 |
| 1109. 航班预订统计 | 中等 | 差分累加座位数，本题「铺满再减」的简化版 |
| 1094. 拼车 | 中等 | 差分记录乘客上下车，还需检查前缀和是否越过容量上限 |
| 560. 和为 K 的子数组 | 中等 | 同属前缀和家族，但用哈希查历史前缀而非在值域上做差分 |
| 1031. 两个无重叠子数组的最大和 | 中等 | 前缀和 + 枚举分界点，体会「枚举一个量再 $O(1)$ 求代价」的套路 |