有序数组中差绝对值之和 图解题解
这道题到底在问什么
- 输入
- nums=[2,3,5]
- 输出
- [4,3,5]
- 输入
- nums=[1,4,6,8,10]
- 输出
- [24,15,13,15,21]
- 输入
- nums=[1,1,1]
- 输出
- [0,0,0]
先想最直接的笨办法
把刚才的暴力换算成公式。左边有 2 个数,它们贡献的是「2 个 4 减去这 2 个数的和」,也就是 2 乘 4 减去前缀和 1 加 2,等于 8 减 3 等于 5;右边有 2 个数,它们贡献「这 2 个数的和减去 2 个 4」,也就是 5 加 6 减去 2 乘 4,等于 11 减 8 等于 3。合计还是 8,和暴力对得上。下面就用这套左右贡献公式,让前缀和累加器从左滚一遍,把五个下标全算出来。（动画第 7 步）
最优解：一步一步想明白
- 3记牢一句:有序数组里,左边都更小、右边都更大,绝对值能直接去符号。result[i] = 左贡献(i×nums[i] − 前缀和) + 右贡献(后缀和 − (n-1-i)×nums[i])。下面每帧都在套这句。
- 4先看清画面。上面是有序数组 nums = [1,2,4,5,6],一共 5 个数。右边那张表是要填的 result,现在还是空的。先把全部元素的总和 s 算出来,1 加 2 加 4 加 5 加 6 等于 18,这个总和等下算右边后缀和时要用。准备好后,从下标 0 开始。
- 5先用最直白的方式感受 result[i] 是什么。看下标 0 的元素 1,它是最小的,其他四个数全在它右边,绿色标出来。result[0] 就是 1 到这四个数的距离之和:到 2 是 1,到 4 是 3,到 5 是 4,到 6 是 5,加起来 13。最左端没有左邻居,这一项天然只有右边。
- 6再看中间的下标 2,元素是 4。它左边有 1 和 2,右边有 5 和 6。因为数组有序,左边两个都比 4 小,距离就是 4 减它们,得到 3 加 2 等于 5;右边两个都比 4 大,距离就是它们减 4,得到 1 加 2 等于 3。两块合起来 result[2] = 8。注意左块全是「4 减左边」,右块全是「右边减 4」,这就是有序能去绝对值的好处。
- 7把刚才的暴力换算成公式。左边有 2 个数,它们贡献的是「2 个 4 减去这 2 个数的和」,也就是 2 乘 4 减去前缀和 1 加 2,等于 8 减 3 等于 5;右边有 2 个数,它们贡献「这 2 个数的和减去 2 个 4」,也就是 5 加 6 减去 2 乘 4,等于 11 减 8 等于 3。合计还是 8,和暴力对得上。下面就用这套左右贡献公式,让前缀和累加器从左滚一遍,把五个下标全算出来。
- 8轮到下标 0,元素是 1。它最左,左边一个数都没有,前缀和 t 此刻是 0,左贡献 = 0 乘 1 减 0 等于 0。这一项为 0,合理,因为没有左邻居要算距离。
- 9再看右边 4 个数(绿色)。它们的和就是后缀和,用总和 18 减去左边前缀和 0,再减去当前元素自己 1,等于 17。右贡献 = 后缀和减去 4 个 1,也就是 17 减 4 等于 13。
- 10把左贡献 0 和右贡献 13 加起来,result[0] = 13,写进右边表里(这一行高亮),当前格标成绿色表示已处理。最后别忘了把当前元素 1 加进前缀和,t 从 0 变成 1,留给下一个下标用。注意先算 result 再更新 t,顺序不能反,否则会把自己也算进左边。
- 11轮到下标 1,元素是 2。它左边有 1 个数(绿色),这些数的和也就是前缀和 t 已经攒到 1。左贡献 = 1 个 2 减去前缀和,也就是 1 乘 2 减 1,等于 2 减 1 等于 1。
- 12再看右边 3 个数(绿色)。它们的和就是后缀和,用总和 18 减去左边前缀和 1,再减去当前元素自己 2,等于 15。右贡献 = 后缀和减去 3 个 2,也就是 15 减 6 等于 9。
- 13把左贡献 1 和右贡献 9 加起来,result[1] = 10,写进右边表里(这一行高亮),当前格标成绿色表示已处理。最后别忘了把当前元素 2 加进前缀和,t 从 1 变成 3,留给下一个下标用。注意先算 result 再更新 t,顺序不能反,否则会把自己也算进左边。
- 14轮到下标 2,元素是 4。它左边有 2 个数(绿色),这些数的和也就是前缀和 t 已经攒到 3。左贡献 = 2 个 4 减去前缀和,也就是 2 乘 4 减 3,等于 8 减 3 等于 5。
- 15再看右边 2 个数(绿色)。它们的和就是后缀和,用总和 18 减去左边前缀和 3,再减去当前元素自己 4,等于 11。右贡献 = 后缀和减去 2 个 4,也就是 11 减 8 等于 3。
- 16把左贡献 5 和右贡献 3 加起来,result[2] = 8,写进右边表里(这一行高亮),当前格标成绿色表示已处理。最后别忘了把当前元素 4 加进前缀和,t 从 3 变成 7,留给下一个下标用。注意先算 result 再更新 t,顺序不能反,否则会把自己也算进左边。
- 17轮到下标 3,元素是 5。它左边有 3 个数(绿色),这些数的和也就是前缀和 t 已经攒到 7。左贡献 = 3 个 5 减去前缀和,也就是 3 乘 5 减 7,等于 15 减 7 等于 8。
- 18再看右边 1 个数(绿色)。它们的和就是后缀和,用总和 18 减去左边前缀和 7,再减去当前元素自己 5,等于 6。右贡献 = 后缀和减去 1 个 5,也就是 6 减 5 等于 1。
- 19把左贡献 8 和右贡献 1 加起来,result[3] = 9,写进右边表里(这一行高亮),当前格标成绿色表示已处理。最后别忘了把当前元素 5 加进前缀和,t 从 7 变成 12,留给下一个下标用。注意先算 result 再更新 t,顺序不能反,否则会把自己也算进左边。
- 20轮到下标 4,元素是 6。它左边有 4 个数(绿色),这些数的和也就是前缀和 t 已经攒到 12。左贡献 = 4 个 6 减去前缀和,也就是 4 乘 6 减 12,等于 24 减 12 等于 12。
- 21它右边没有元素了。右边后缀和 = 总和 18 减前缀和 12 再减它自己 6,等于 0;右贡献 = 0 减 0 个 6 等于 0。最右端右贡献为 0,符合预期。
- 22把左贡献 12 和右贡献 0 加起来,result[4] = 12,写进右边表里(这一行高亮),当前格标成绿色表示已处理。五个下标全部算完。前缀和此刻滚到了 18,正好等于总和 18。
- 23五个下标都填满了,回看一遍:13、10、8、9、12。每一个都是「左贡献加右贡献」,而左右两块各自靠前缀和与后缀和一步算出,前缀和累加器从 0 一路滚到 18,全程只扫了一遍。最终 result = [13,10,8,9,12]。整道题的窍门就一句:有序去绝对值,再用前缀和拆成左右两块贡献。
⚠️ 容易写错的地方
✗ 错：不顾有序前提,硬把 |nums[i]-nums[j]| 当黑盒,退回两层循环逐个求绝对值
✓ 对：先认准数组非递减:左边都 ≤ 当前、右边都 ≥ 当前,绝对值直接去符号拆成左右两块
这道题的全部加速都建立在「有序」上。有序了,左边的差恒为 nums[i]-nums[j]、右边恒为 nums[j]-nums[i],才能用前缀和与后缀和一次性求和。若数组无序,这套拆分不成立,只能老实两层循环或先排序
✗ 错：先更新前缀和再算 result[i],把当前元素自己也算进了左边的和
✓ 对：严格先用旧的前缀和 t 算出 result[i],再执行 t += nums[i]
t 的含义是「下标 i 之前那些数的和」,不含 nums[i] 自己。如果先加了 nums[i],t 就变成含自己的和,左贡献里会多减一份 nums[i],结果偏小。顺序必须是先算后加
✗ 错：把左右两边的元素个数数错,右边用了 n-i 个、把当前元素也算进去
✓ 对：左边 j 小于 i 共 i 个数,右边 j 大于 i 共 n-1-i 个数,当前元素自己不算
当前下标 i 把数组切成三段:左边 i 个、自己 1 个、右边 n-1-i 个。右贡献里要减的是 n-1-i 个 nums[i],少减或多减一份都会让答案差一个 nums[i]。先把三段个数掰清楚再套公式
完整代码（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 getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
ans = []
s, t = sum(nums), 0
for i, x in enumerate(nums):
v = x * i - t + s - t - x * (len(nums) - i)
ans.append(v)
t += x
return ansC++
#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:
vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
int s = accumulate(nums.begin(), nums.end(), 0), t = 0;
int n = nums.size();
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
int v = nums[i] * i - t + s - t - nums[i] * (n - i);
ans[i] = v;
t += nums[i];
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int[] getSumAbsoluteDifferences(int[] nums) {
// int s = Arrays.stream(nums).sum();
int s = 0, t = 0;
for (int x : nums) {
s += x;
}
int n = nums.length;
int[] ans = new int[n];
for (int i = 0; i < n; ++i) {
int v = nums[i] * i - t + s - t - nums[i] * (n - i);
ans[i] = v;
t += nums[i];
}
return ans;
}
}复杂度
时间
O(n)
n 是数组长度。先一遍求总和是 O(n),再一遍从左到右算每个下标的左右贡献,每格只做常数次加减乘,又是 O(n),合起来仍是线性 O(n)。相比每个下标都跟所有人比一遍的两层循环 O(n²),前缀和把它降了一个量级
空间
O(1) / O(n)
按峰值算。额外只用了总和 s、前缀和累加器 t 两个变量,是常数 O(1)。返回的 result 数组长度为 n,那是必须交出去的输出,若把它计入则是 O(n);核心计算逻辑本身只需常数额外空间
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 有序数组中差绝对值之和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
如果数组没排序,这套前缀和拆分还能用吗?+
不能直接用。整套加速的前提就是有序,有序才能保证左边的差恒为 nums[i]-nums[j]、右边恒为 nums[j]-nums[i],符号固定下来才能用前缀和与后缀和成段求和。如果输入无序,要么老老实实两层循环逐个取绝对值求和,那是 O(n²);要么先排序变成有序再套这套公式,但排序会打乱下标,如果题目要求按原下标输出,还得记住每个元素原来的位置,排完再映射回去。本题题面保证了非递减,所以省去排序,直接一遍扫描。
前缀和这个工具一般还能解什么类型的题?+
前缀和是非常基础的预处理工具,核心价值是把「反复求某一段的和」从每次重新累加降到常数时间。最典型的就是区间和:预处理出前缀和后,任意区间 [l,r] 的和等于 prefix[r+1] 减 prefix[l],O(1) 拿到。它还能扩展到二维区域和、和为定值的子数组计数(配合哈希表)、以及本题这种把绝对差按符号分段求和。看到「频繁查询区间累计量」就该想到前缀和。
结果会不会溢出,要不要用 long?+
看数据范围。本题给定约束下,元素值和数组长度都不大,result[i] 最大也就在十亿出头的量级,没有超过 int 能表示的范围,所以参考代码三种语言都用 int 就够了。但如果把题目的值域或长度放大,比如元素到 1e9、长度到 1e5,那么 i×nums[i] 或后缀和很容易突破 int 上界,这时就必须换成 long(C++ 的 long long、Java 的 long)来防溢出。面试时主动说一句「按当前约束 int 够用,放大范围要换 long」会显得很稳。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 有序数组中差绝对值之和 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。