有序数组中差绝对值之和

记牢一句:有序数组里,左边都更小、右边都更大,绝对值能直接去符号。result[i] = 左贡献(i×nums[i] − 前缀和) + 右贡献(后缀和 − (n-1-i)×nums[i])。下面每帧都在套这句。

总览 · 源数组 + 总和 s = 18：先看清画面。上面是有序数组 nums = [1,2,4,5,6],一共 5 个数。右边那张表是要填的 result,现在还是空的。先把全部元素的总和 s 算出来,1 加 2 加 4 加 5 加 6 等于 18,这个总和等下算右边后缀和时要用。准备好后,从下标 0 开始。

暴力理解 · result[0] = 13：先用最直白的方式感受 result[i] 是什么。看下标 0 的元素 1,它是最小的,其他四个数全在它右边,绿色标出来。result[0] 就是 1 到这四个数的距离之和:到 2 是 1,到 4 是 3,到 5 是 4,到 6 是 5,加起来 13。最左端没有左邻居,这一项天然只有右边。

暴力理解 · result[2] = 8：再看中间的下标 2,元素是 4。它左边有 1 和 2,右边有 5 和 6。因为数组有序,左边两个都比 4 小,距离就是 4 减它们,得到 3 加 2 等于 5;右边两个都比 4 大,距离就是它们减 4,得到 1 加 2 等于 3。两块合起来 result[2] = 8。注意左块全是「4 减左边」,右块全是「右边减 4」,这就是有序能去绝对值的好处。

公式验证 · result[2] = 5 + 3 = 8：把刚才的暴力换算成公式。左边有 2 个数,它们贡献的是「2 个 4 减去这 2 个数的和」,也就是 2 乘 4 减去前缀和 1 加 2,等于 8 减 3 等于 5;右边有 2 个数,它们贡献「这 2 个数的和减去 2 个 4」,也就是 5 加 6 减去 2 乘 4,等于 11 减 8 等于 3。合计还是 8,和暴力对得上。下面就用这套左右贡献公式,让前缀和累加器从左滚一遍,把五个下标全算出来。

下标 0 · 左贡献 = 0：轮到下标 0,元素是 1。它最左,左边一个数都没有,前缀和 t 此刻是 0,左贡献 = 0 乘 1 减 0 等于 0。这一项为 0,合理,因为没有左邻居要算距离。

下标 0 · 右贡献 = 13：再看右边 4 个数(绿色)。它们的和就是后缀和,用总和 18 减去左边前缀和 0,再减去当前元素自己 1,等于 17。右贡献 = 后缀和减去 4 个 1,也就是 17 减 4 等于 13。

下标 0 · result = 13：把左贡献 0 和右贡献 13 加起来,result[0] = 13,写进右边表里(这一行高亮),当前格标成绿色表示已处理。最后别忘了把当前元素 1 加进前缀和,t 从 0 变成 1,留给下一个下标用。注意先算 result 再更新 t,顺序不能反,否则会把自己也算进左边。

下标 1 · 左贡献 = 1：轮到下标 1,元素是 2。它左边有 1 个数(绿色),这些数的和也就是前缀和 t 已经攒到 1。左贡献 = 1 个 2 减去前缀和,也就是 1 乘 2 减 1,等于 2 减 1 等于 1。

下标 1 · 右贡献 = 9：再看右边 3 个数(绿色)。它们的和就是后缀和,用总和 18 减去左边前缀和 1,再减去当前元素自己 2,等于 15。右贡献 = 后缀和减去 3 个 2,也就是 15 减 6 等于 9。

下标 1 · result = 10：把左贡献 1 和右贡献 9 加起来,result[1] = 10,写进右边表里(这一行高亮),当前格标成绿色表示已处理。最后别忘了把当前元素 2 加进前缀和,t 从 1 变成 3,留给下一个下标用。注意先算 result 再更新 t,顺序不能反,否则会把自己也算进左边。

下标 2 · 左贡献 = 5：轮到下标 2,元素是 4。它左边有 2 个数(绿色),这些数的和也就是前缀和 t 已经攒到 3。左贡献 = 2 个 4 减去前缀和,也就是 2 乘 4 减 3,等于 8 减 3 等于 5。

下标 2 · 右贡献 = 3：再看右边 2 个数(绿色)。它们的和就是后缀和,用总和 18 减去左边前缀和 3,再减去当前元素自己 4,等于 11。右贡献 = 后缀和减去 2 个 4,也就是 11 减 8 等于 3。

下标 2 · result = 8：把左贡献 5 和右贡献 3 加起来,result[2] = 8,写进右边表里(这一行高亮),当前格标成绿色表示已处理。最后别忘了把当前元素 4 加进前缀和,t 从 3 变成 7,留给下一个下标用。注意先算 result 再更新 t,顺序不能反,否则会把自己也算进左边。

下标 3 · 左贡献 = 8：轮到下标 3,元素是 5。它左边有 3 个数(绿色),这些数的和也就是前缀和 t 已经攒到 7。左贡献 = 3 个 5 减去前缀和,也就是 3 乘 5 减 7,等于 15 减 7 等于 8。

下标 3 · 右贡献 = 1：再看右边 1 个数(绿色)。它们的和就是后缀和,用总和 18 减去左边前缀和 7,再减去当前元素自己 5,等于 6。右贡献 = 后缀和减去 1 个 5,也就是 6 减 5 等于 1。

下标 3 · result = 9：把左贡献 8 和右贡献 1 加起来,result[3] = 9,写进右边表里(这一行高亮),当前格标成绿色表示已处理。最后别忘了把当前元素 5 加进前缀和,t 从 7 变成 12,留给下一个下标用。注意先算 result 再更新 t,顺序不能反,否则会把自己也算进左边。

下标 4 · 左贡献 = 12：轮到下标 4,元素是 6。它左边有 4 个数(绿色),这些数的和也就是前缀和 t 已经攒到 12。左贡献 = 4 个 6 减去前缀和,也就是 4 乘 6 减 12,等于 24 减 12 等于 12。

下标 4 · 右贡献 = 0：它右边没有元素了。右边后缀和 = 总和 18 减前缀和 12 再减它自己 6,等于 0;右贡献 = 0 减 0 个 6 等于 0。最右端右贡献为 0,符合预期。

下标 4 · result = 12：把左贡献 12 和右贡献 0 加起来,result[4] = 12,写进右边表里(这一行高亮),当前格标成绿色表示已处理。五个下标全部算完。前缀和此刻滚到了 18,正好等于总和 18。

完成 · result = [13,10,8,9,12]：五个下标都填满了,回看一遍:13、10、8、9、12。每一个都是「左贡献加右贡献」,而左右两块各自靠前缀和与后缀和一步算出,前缀和累加器从 0 一路滚到 18,全程只扫了一遍。最终 result = [13,10,8,9,12]。整道题的窍门就一句:有序去绝对值,再用前缀和拆成左右两块贡献。

边界:全相等时距离全 0、结果全 0;重复值不用特判;只有两个数时每个下标只有一边邻居,另一边贡献为 0。

面试重点:无序则不能直接拆(需排序并记原下标);前缀和擅长区间和、子数组计数等「频繁查累计量」的题;本题约束内 int 够用,值域放大要换 long 防溢出。