LeetCode 1674中等数组 · 哈希
使数组互补的最少操作次数 图解题解
这道题到底在问什么
给定偶数长度数组 nums 与上限 limit。每次操作可把某个元素改成 1 到 limit 之间的另一个整数。若对所有下标 i 都有 nums[i] 加 nums[n 减 1 减 i] 等于同一个值,则数组互补。求让数组互补的最少操作次数。
- 输入
- nums = [1,2,4,3], limit = 4
- 输出
- 1(把 4 改成 2,两对的和都成 4)
- 输入
- nums = [1,2,2,1], limit = 2
- 输出
- 2(只能在 1 到 2 里改,要改两次都凑成 4)
- 输入
- nums = [1,2,1,2], limit = 2
- 输出
- 0(两对和都已是 3,无需操作)
最优解：一步一步想明白
- 3记牢这条主线:目标和 T 从 2 到 2 倍 limit 一个个试;对每一对,凑成 T 要么 0 次、要么 1 次、要么 2 次,而且只在 4 个断点处变。所以用差分数组在断点处记一笔,叠加完所有对再做前缀和,每个目标和要多少次操作就一目了然,最少的就是答案。下面每一帧都在套这条线。
- 4先把数组首尾配对。绿色这一对是下标 0 和下标 3,也就是 1 和 3,和是 4;底色框出的另一对是下标 1 和下标 2,也就是 2 和 4,和是 6。现在两对的和一个是 4、一个是 6,并不相等,所以不互补。每个数都在 1 到 limit 也就是 1 到 4 之间,所以两数之和最小是 1 加 1 等于 2、最大是 4 加 4 等于 8。目标和只可能落在 2 到 8 这 7 个值里,我们要做的就是在这 7 个目标里挑一个最省操作的。
- 5右边这张表就是差分数组 d,它的每一行对应一个目标和,从 2 排到 8。最后那行和 9 是参考代码里多开的一个溢出槽,因为有的断点会落到 9 这个位置,而最大可能和只有 8,所以和 9 这一行只用来接住越界的记账,它不是有效目标,即使某些实现扫到它,那一格的值也只会更大,不影响最小值。现在所有格子都是 0。接下来每一对都来这张表上记账:在它的几个断点处加加减减。两对都记完,再把这张表做前缀和,就得到每个目标和实际要花的操作数。
- 6处理第 1 对,绿色高亮的是下标 0 和下标 3 这两个数 1 和 3。先排个大小:较小的记作 a 等于 1,较大的记作 b 等于 3,它俩当前的和是 a 加 b 等于 4。下面要做的,就是把这一对在每个目标和下要花几次操作,通过 4 个断点记到差分表里。先想清楚一件事:留着一个数不动、只改另一个,这对的和能覆盖从 a 加 1 到 b 加 limit 这一整段,这段里只需 1 次。
- 7第一步起底:在目标和 2 这一行加 2。差分数组里在最左端加 2,意思是从最小的目标和起,先悲观地假设这一对要两个数都改、记 2 次,后面再用减法把该省的省回来。这是差分的常见手法:先按最坏情形铺一层底,再在断点处往下调。现在 d 在和 2 这一行变成了 2。
- 8第二步降一档:在目标和 a 加 1 也就是 2 这一行减 1。因为目标和只要落在 a 加 1 到 b 加 limit 这一整段里,就能靠保留其中一个数、修改另一个数来凑成:低端保留较小的 a、改另一个,高端保留较大的 b、改另一个,一次操作就够,不必两个都动。差分里在 2 处减 1,代表从这个目标和起,操作数都比刚才那层底少 1,也就是从 2 次降到 1 次。
- 9第三步降到 0 次:在目标和等于当前和 a 加 b 也就是 4 这一行再减 1。道理很直白:如果目标和恰好就是这对现在的和 4,那它俩本来就满足,一次操作都不用做。所以在 4 这一个点上,操作数要在 1 次的基础上再降 1,变成 0 次。注意这只是 4 这一个单点降到 0 次,下一帧就要把它弹回去。
- 10第四步弹回:在目标和 a 加 b 加 1 也就是 5 这一行加 1。上一帧的 0 次特例只针对当前和 4 这一个点,目标和一旦比 4 大,就又得改一个数才能凑到,操作数从 0 次回到 1 次。差分里用加 1 把刚才减掉的补回来,保证 0 次只发生在 4 那一个格子,左右两边仍是 1 次。
- 11第五步升二档:在目标和 b 加 limit 加 1 也就是 8 这一行加 1。当目标和大到超过 b 加 limit 等于 7,就连改一个数也凑不到了,必须两个都改,操作数从 1 次回到 2 次。差分里在 8 处加 1 把它抬回 2 次。到这,第 1 对 的账就记完了,四个断点全部到位。
- 12处理第 2 对,绿色高亮的是下标 1 和下标 2 这两个数 2 和 4。先排个大小:较小的记作 a 等于 2,较大的记作 b 等于 4,它俩当前的和是 a 加 b 等于 6。下面要做的,就是把这一对在每个目标和下要花几次操作,通过 4 个断点记到差分表里。先想清楚一件事:留着一个数不动、只改另一个,这对的和能覆盖从 a 加 1 到 b 加 limit 这一整段,这段里只需 1 次。
- 13第一步起底:在目标和 2 这一行加 2。差分数组里在最左端加 2,意思是从最小的目标和起,先悲观地假设这一对要两个数都改、记 2 次,后面再用减法把该省的省回来。这是差分的常见手法:先按最坏情形铺一层底,再在断点处往下调。现在 d 在和 2 这一行变成了 3。
- 14第二步降一档:在目标和 a 加 1 也就是 3 这一行减 1。因为目标和只要落在 a 加 1 到 b 加 limit 这一整段里,就能靠保留其中一个数、修改另一个数来凑成:低端保留较小的 a、改另一个,高端保留较大的 b、改另一个,一次操作就够,不必两个都动。差分里在 3 处减 1,代表从这个目标和起,操作数都比刚才那层底少 1,也就是从 2 次降到 1 次。
- 15第三步降到 0 次:在目标和等于当前和 a 加 b 也就是 6 这一行再减 1。道理很直白:如果目标和恰好就是这对现在的和 6,那它俩本来就满足,一次操作都不用做。所以在 6 这一个点上,操作数要在 1 次的基础上再降 1,变成 0 次。注意这只是 6 这一个单点降到 0 次,下一帧就要把它弹回去。
- 16第四步弹回:在目标和 a 加 b 加 1 也就是 7 这一行加 1。上一帧的 0 次特例只针对当前和 6 这一个点,目标和一旦比 6 大,就又得改一个数才能凑到,操作数从 0 次回到 1 次。差分里用加 1 把刚才减掉的补回来,保证 0 次只发生在 6 那一个格子,左右两边仍是 1 次。
- 17第五步升二档:在目标和 b 加 limit 加 1 也就是 9 这一行加 1。当目标和大到超过 b 加 limit 等于 8,就连改一个数也凑不到了,必须两个都改,操作数从 1 次回到 2 次。这一对的这个断点落在了 9,已经超过最大可能和 8,它进了那个溢出槽,不是有效目标,即使某些实现扫到它也只会更大,不影响最小值,记上只是为了和参考代码完全对齐。到这,第 2 对 的账就记完了,四个断点全部到位。
- 18两对都记完账了,它们的加减都落在同一张差分表上,叠加成了现在这个样子:从和 2 到和 9,数值依次是 3、-1、-1、1、-1、1、1、1。差分本身还不是答案,它记的是相邻目标和之间操作数的增减量。下一步要做的,就是从和 2 开始往右做前缀和,把这些增减量累加起来,每累加到一个目标和,得到的就是这个目标和下两对加起来一共要花几次操作。
- 19把差分从左往右累加到目标和 2。第一格直接取差分值,目标和 2 处两对加起来需要 3 次操作,先把它当作目前的最少。这个 3 比之前见过的都小,于是把最少操作数刷新成 3,眼下最划算的目标和是 2。继续往右看下一个目标和。
- 20把差分从左往右累加到目标和 3。在上一格的基础上加上 3 这里的差分 -1,得到把两对都凑成目标和 3 总共需要 2 次操作。这个 2 比之前见过的都小,于是把最少操作数刷新成 2,眼下最划算的目标和是 3。继续往右看下一个目标和。
- 21把差分从左往右累加到目标和 4。在上一格的基础上加上 4 这里的差分 -1,得到把两对都凑成目标和 4 总共需要 1 次操作。这个 1 比之前见过的都小,于是把最少操作数刷新成 1,眼下最划算的目标和是 4。继续往右看下一个目标和。
- 22把差分从左往右累加到目标和 5。在上一格的基础上加上 5 这里的差分 1,得到把两对都凑成目标和 5 总共需要 2 次操作。这个 2 没比之前的最少 1 更小,所以最少操作数保持 1 不变。继续往右看下一个目标和。
- 23把差分从左往右累加到目标和 6。在上一格的基础上加上 6 这里的差分 -1,得到把两对都凑成目标和 6 总共需要 1 次操作。这个 1 没比之前的最少 1 更小,所以最少操作数保持 1 不变。继续往右看下一个目标和。
- 24把差分从左往右累加到目标和 7。在上一格的基础上加上 7 这里的差分 1,得到把两对都凑成目标和 7 总共需要 2 次操作。这个 2 没比之前的最少 1 更小,所以最少操作数保持 1 不变。继续往右看下一个目标和。
- 25把差分从左往右累加到目标和 8。在上一格的基础上加上 8 这里的差分 1,得到把两对都凑成目标和 8 总共需要 3 次操作。这个 3 没比之前的最少 1 更小,所以最少操作数保持 1 不变。这 7 个候选目标和到这全扫完,最少操作数是 1 次。
- 26从目标和 2 一路扫到 8,每个目标和要多少次操作都算出来了,最少的是 1 次,在目标和 4 和 6 处取得。拿目标和 4 来对一下:第一对 1 和 3 本来和就是 4,不用动;第二对 2 和 4 的和是 6,把那个 4 改成 2,就变成 2 加 2 等于 4,一次操作。两对都成了和 4,数组互补,总共只花 1 次,和答案对上了。整个过程没有去试遍所有改法,而是把每个目标和的代价用差分加前缀和快速算了出来。
⚠️ 容易写错的地方
✗ 错：只在原数组现有的几个和里挑目标
✓ 对：目标和要在 2 到 2 倍 limit 之间整段枚举
最优目标和未必等于某一对现在的和,可能是个谁都没出现过的中间值,只有把整段都比一遍才不漏
✗ 错：对每个目标和都重新累加每一对的代价
✓ 对：用差分在 4 个断点上加减,一次覆盖一整段
逐个目标乘逐对是 O(n 乘 limit),limit 大就慢;差分让每对只动常数个端点,再一遍前缀和摊平到线性
✗ 错：差分数组开成 2 倍 limit 大小就够
✓ 对：要开 2 倍 limit 加 2,断点 b 加 limit 加 1 最大会到 2 倍 limit 加 1
较大数 b 最大是 limit,断点 b 加 limit 加 1 就到 2 倍 limit 加 1,数组不够长会越界,所以要多留两格
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
def minMoves(self, nums: List[int], limit: int) -> int:
d = [0] * (2 * limit + 2)
n = len(nums)
for i in range(n // 2):
x, y = nums[i], nums[-i - 1]
if x > y:
x, y = y, x
d[2] += 2
d[x + 1] -= 2
d[x + 1] += 1
d[x + y] -= 1
d[x + y + 1] += 1
d[y + limit + 1] -= 1
d[y + limit + 1] += 2
return min(accumulate(d[2:]))C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int minMoves(vector<int>& nums, int limit) {
int n = nums.size();
int d[limit * 2 + 2];
memset(d, 0, sizeof(d));
for (int i = 0; i < n / 2; ++i) {
int x = nums[i], y = nums[n - i - 1];
if (x > y) {
swap(x, y);
}
d[2] += 2;
d[x + 1] -= 2;
d[x + 1] += 1;
d[x + y] -= 1;
d[x + y + 1] += 1;
d[y + limit + 1] -= 1;
d[y + limit + 1] += 2;
}
int ans = n;
for (int i = 2, s = 0; i <= limit * 2; ++i) {
s += d[i];
ans = min(ans, s);
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int minMoves(int[] nums, int limit) {
int[] d = new int[2 * limit + 2];
int n = nums.length;
for (int i = 0; i < n / 2; ++i) {
int x = Math.min(nums[i], nums[n - i - 1]);
int y = Math.max(nums[i], nums[n - i - 1]);
d[2] += 2;
d[x + 1] -= 2;
d[x + 1] += 1;
d[x + y] -= 1;
d[x + y + 1] += 1;
d[y + limit + 1] -= 1;
d[y + limit + 1] += 2;
}
int ans = n;
for (int i = 2, s = 0; i < d.length; ++i) {
s += d[i];
ans = Math.min(ans, s);
}
return ans;
}
}复杂度
时间
O(n + limit)
遍历 n / 2 对各记常数笔差分,是 O(n);再扫一遍长度约 2 倍 limit 的差分数组做前缀和取最小,是 O(limit);合起来线性级别
空间
O(limit)
峰值占用是那个差分数组 d,长度 2 倍 limit 加 2,与 limit 成正比;其余只用了几个标量。不是 O(1)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 使数组互补的最少操作次数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
最朴素的做法是什么,为什么慢?+
最朴素就是把目标和从 2 到 2 倍 limit 一个个试,对每个目标和再遍历所有 n 半对,算每一对凑成它要几次操作,把代价加起来取最小。这样是目标和的个数乘以对数,也就是 O(limit 乘 n),limit 上万时就偏慢。差分法的关键是看出每一对的代价对目标和是分段常数,只在四个断点变,于是用差分把每对的贡献摊到端点,再一遍前缀和,总复杂度降到 O(n 加 limit)。
为什么一对的操作数只会是 0、1、2 三种?+
因为一对里只有两个数。两个都不改,只有目标和恰好等于现在的和时成立,是 0 次;改一个数,能把和挪到 a 加 1 到 b 加 limit 这一整段连续值,是 1 次;两个都改,任意 2 到 2 倍 limit 的和都能凑出来,是 2 次。再没有第四种情况,所以代价天然分成这三档,对应差分上那几个断点。
差分数组为什么要开 2 倍 limit 加 2 那么大?+
答案要扫的目标和是 2 到 2 倍 limit。但差分里有个断点是 b 加 limit 加 1,而 b 最大能到 limit,所以这个断点最大会到 2 倍 limit 加 1,超出了扫描范围。为了让这笔记账有地方落、不越界,数组要一直开到 2 倍 limit 加 1 这个下标,也就是长度 2 倍 limit 加 2。这个多出来的格子不是有效目标,即使某些实现扫到它也只会更大、不影响最小值,纯粹是接住越界的端点。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 使数组互补的最少操作次数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。