题目描述
思路解析动画文字版
记牢这条主线:目标和 T 从 2 到 2 倍 limit 一个个试;对每一对,凑成 T 要么 0 次、要么 1 次、要么 2 次,而且只在 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 个目标里挑一个最省操作的。
初始化 · 差分数组按目标和清零：右边这张表就是差分数组 d,它的每一行对应一个目标和,从 2 排到 8。最后那行和 9 是参考代码里多开的一个溢出槽,因为有的断点会落到 9 这个位置,而最大可能和只有 8,所以和 9 这一行只用来接住越界的记账,它不是有效目标,即使某些实现扫到它,那一格的值也只会更大,不影响最小值。现在所有格子都是 0。接下来每一对都来这张表上记账:在它的几个断点处加加减减。两对都记完,再把这张表做前缀和,就得到每个目标和实际要花的操作数。
第 1 对 · 取出这一对：处理第 1 对,绿色高亮的是下标 0 和下标 3 这两个数 1 和 3。先排个大小:较小的记作 a 等于 1,较大的记作 b 等于 3,它俩当前的和是 a 加 b 等于 4。下面要做的,就是把这一对在每个目标和下要花几次操作,通过 4 个断点记到差分表里。先想清楚一件事:留着一个数不动、只改另一个,这对的和能覆盖从 a 加 1 到 b 加 limit 这一整段,这段里只需 1 次。
第 1 对 · 起底记 2 次：第一步起底:在目标和 2 这一行加 2。差分数组里在最左端加 2,意思是从最小的目标和起,先悲观地假设这一对要两个数都改、记 2 次,后面再用减法把该省的省回来。这是差分的常见手法:先按最坏情形铺一层底,再在断点处往下调。现在 d 在和 2 这一行变成了 2。
第 1 对 · 从 a+1 降到 1 次：第二步降一档:在目标和 a 加 1 也就是 2 这一行减 1。因为目标和只要落在 a 加 1 到 b 加 limit 这一整段里,就能靠保留其中一个数、修改另一个数来凑成:低端保留较小的 a、改另一个,高端保留较大的 b、改另一个,一次操作就够,不必两个都动。差分里在 2 处减 1,代表从这个目标和起,操作数都比刚才那层底少 1,也就是从 2 次降到 1 次。
第 1 对 · 当前和这格 0 次：第三步降到 0 次:在目标和等于当前和 a 加 b 也就是 4 这一行再减 1。道理很直白:如果目标和恰好就是这对现在的和 4,那它俩本来就满足,一次操作都不用做。所以在 4 这一个点上,操作数要在 1 次的基础上再降 1,变成 0 次。注意这只是 4 这一个单点降到 0 次,下一帧就要把它弹回去。
第 1 对 · 过了当前和回到 1 次：第四步弹回:在目标和 a 加 b 加 1 也就是 5 这一行加 1。上一帧的 0 次特例只针对当前和 4 这一个点,目标和一旦比 4 大,就又得改一个数才能凑到,操作数从 0 次回到 1 次。差分里用加 1 把刚才减掉的补回来,保证 0 次只发生在 4 那一个格子,左右两边仍是 1 次。
第 1 对 · 太大回到 2 次：第五步升二档:在目标和 b 加 limit 加 1 也就是 8 这一行加 1。当目标和大到超过 b 加 limit 等于 7,就连改一个数也凑不到了,必须两个都改,操作数从 1 次回到 2 次。差分里在 8 处加 1 把它抬回 2 次。到这,第 1 对 的账就记完了,四个断点全部到位。
第 2 对 · 取出这一对：处理第 2 对,绿色高亮的是下标 1 和下标 2 这两个数 2 和 4。先排个大小:较小的记作 a 等于 2,较大的记作 b 等于 4,它俩当前的和是 a 加 b 等于 6。下面要做的,就是把这一对在每个目标和下要花几次操作,通过 4 个断点记到差分表里。先想清楚一件事:留着一个数不动、只改另一个,这对的和能覆盖从 a 加 1 到 b 加 limit 这一整段,这段里只需 1 次。
第 2 对 · 起底记 2 次：第一步起底:在目标和 2 这一行加 2。差分数组里在最左端加 2,意思是从最小的目标和起,先悲观地假设这一对要两个数都改、记 2 次,后面再用减法把该省的省回来。这是差分的常见手法:先按最坏情形铺一层底,再在断点处往下调。现在 d 在和 2 这一行变成了 3。
第 2 对 · 从 a+1 降到 1 次：第二步降一档:在目标和 a 加 1 也就是 3 这一行减 1。因为目标和只要落在 a 加 1 到 b 加 limit 这一整段里,就能靠保留其中一个数、修改另一个数来凑成:低端保留较小的 a、改另一个,高端保留较大的 b、改另一个,一次操作就够,不必两个都动。差分里在 3 处减 1,代表从这个目标和起,操作数都比刚才那层底少 1,也就是从 2 次降到 1 次。
第 2 对 · 当前和这格 0 次：第三步降到 0 次:在目标和等于当前和 a 加 b 也就是 6 这一行再减 1。道理很直白:如果目标和恰好就是这对现在的和 6,那它俩本来就满足,一次操作都不用做。所以在 6 这一个点上,操作数要在 1 次的基础上再降 1,变成 0 次。注意这只是 6 这一个单点降到 0 次,下一帧就要把它弹回去。
第 2 对 · 过了当前和回到 1 次：第四步弹回:在目标和 a 加 b 加 1 也就是 7 这一行加 1。上一帧的 0 次特例只针对当前和 6 这一个点,目标和一旦比 6 大,就又得改一个数才能凑到,操作数从 0 次回到 1 次。差分里用加 1 把刚才减掉的补回来,保证 0 次只发生在 6 那一个格子,左右两边仍是 1 次。
第 2 对 · 太大回到 2 次：第五步升二档:在目标和 b 加 limit 加 1 也就是 9 这一行加 1。当目标和大到超过 b 加 limit 等于 8,就连改一个数也凑不到了,必须两个都改,操作数从 1 次回到 2 次。这一对的这个断点落在了 9,已经超过最大可能和 8,它进了那个溢出槽,不是有效目标,即使某些实现扫到它也只会更大,不影响最小值,记上只是为了和参考代码完全对齐。到这,第 2 对 的账就记完了,四个断点全部到位。
叠加 · 两对的差分合并定型：两对都记完账了,它们的加减都落在同一张差分表上,叠加成了现在这个样子:从和 2 到和 9,数值依次是 3、-1、-1、1、-1、1、1、1。差分本身还不是答案,它记的是相邻目标和之间操作数的增减量。下一步要做的,就是从和 2 开始往右做前缀和,把这些增减量累加起来,每累加到一个目标和,得到的就是这个目标和下两对加起来一共要花几次操作。
前缀和 · 目标和 2 需 3 次：把差分从左往右累加到目标和 2。第一格直接取差分值,目标和 2 处两对加起来需要 3 次操作,先把它当作目前的最少。这个 3 比之前见过的都小,于是把最少操作数刷新成 3,眼下最划算的目标和是 2。继续往右看下一个目标和。
前缀和 · 目标和 3 需 2 次：把差分从左往右累加到目标和 3。在上一格的基础上加上 3 这里的差分 -1,得到把两对都凑成目标和 3 总共需要 2 次操作。这个 2 比之前见过的都小,于是把最少操作数刷新成 2,眼下最划算的目标和是 3。继续往右看下一个目标和。
前缀和 · 目标和 4 需 1 次：把差分从左往右累加到目标和 4。在上一格的基础上加上 4 这里的差分 -1,得到把两对都凑成目标和 4 总共需要 1 次操作。这个 1 比之前见过的都小,于是把最少操作数刷新成 1,眼下最划算的目标和是 4。继续往右看下一个目标和。
前缀和 · 目标和 5 需 2 次：把差分从左往右累加到目标和 5。在上一格的基础上加上 5 这里的差分 1,得到把两对都凑成目标和 5 总共需要 2 次操作。这个 2 没比之前的最少 1 更小,所以最少操作数保持 1 不变。继续往右看下一个目标和。
前缀和 · 目标和 6 需 1 次：把差分从左往右累加到目标和 6。在上一格的基础上加上 6 这里的差分 -1,得到把两对都凑成目标和 6 总共需要 1 次操作。这个 1 没比之前的最少 1 更小,所以最少操作数保持 1 不变。继续往右看下一个目标和。
前缀和 · 目标和 7 需 2 次：把差分从左往右累加到目标和 7。在上一格的基础上加上 7 这里的差分 1,得到把两对都凑成目标和 7 总共需要 2 次操作。这个 2 没比之前的最少 1 更小,所以最少操作数保持 1 不变。继续往右看下一个目标和。
前缀和 · 目标和 8 需 3 次：把差分从左往右累加到目标和 8。在上一格的基础上加上 8 这里的差分 1,得到把两对都凑成目标和 8 总共需要 3 次操作。这个 3 没比之前的最少 1 更小,所以最少操作数保持 1 不变。这 7 个候选目标和到这全扫完,最少操作数是 1 次。
完成 · 最少操作数 1：从目标和 2 一路扫到 8,每个目标和要多少次操作都算出来了,最少的是 1 次,在目标和 4 和 6 处取得。拿目标和 4 来对一下:第一对 1 和 3 本来和就是 4,不用动;第二对 2 和 4 的和是 6,把那个 4 改成 2,就变成 2 加 2 等于 4,一次操作。两对都成了和 4,数组互补,总共只花 1 次,和答案对上了。整个过程没有去试遍所有改法,而是把每个目标和的代价用差分加前缀和快速算了出来。
边界:两对和已相等时答案 0;limit 小到凑不出大和时(如 [1,2,2,1] limit 2)只能逐对改、共 2 次;首尾和天然相等(如 [1,2,3,4] 和都为 5)也是 0。
面试重点:朴素逐目标逐对是 O(limit 乘 n),差分加前缀和压到 O(n 加 limit);一对代价只有 0、1、2 三档对应四个断点;差分要开 2 倍 limit 加 2 接住 b 加 limit 加 1 这个最大断点。
参考代码
from __future__ import annotationsfrom 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:]))复杂度
- 时间：O(n + limit)，遍历 n / 2 对各记常数笔差分,是 O(n);再扫一遍长度约 2 倍 limit 的差分数组做前缀和取最小,是 O(limit);合起来线性级别
- 空间：O(limit)，峰值占用是那个差分数组 d,长度 2 倍 limit 加 2,与 limit 成正比;其余只用了几个标量。不是 O(1)
易错点
面试追问把动画讲成自己的话
追问最朴素的做法是什么,为什么慢?
追问为什么一对的操作数只会是 0、1、2 三种?
追问差分数组为什么要开 2 倍 limit 加 2 那么大?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
有序数组中差绝对值之和
LeetCode 1685 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题