有序数组中差绝对值之和 图解题解

每个 result[i] 在累加哪些距离

给一个从小到大排好、可以有相等值的数组 nums，返回等长的 result，result[i] 是 nums[i] 到各元素的绝对差之和，含自己那项距离 0。题面 nums=[1,4,6,8,10] 答案 [24,15,13,15,21]，如 result[0]=24 就是 1 到 4、6、8、10 的距离和 3+5+7+9。数组已排好序。

逐个求绝对值，n 一大为什么扛不住

照定义硬来，对每个下标 i，把 nums[i] 跟全部 n 个数各求一次绝对差累加。每个下标都扫一遍整个数组，n 个下标就是 n 乘 n 次运算，也就是 O(n²)。n 到几万就窜到几亿次，线性时间根本够不着。

排好序之后，绝对值凭什么能甩掉符号

有序是全部加速的地基。对某个 nums[i]，它左边的数都 ≤ 它、右边都 ≥ 它，绝对值的符号就此钉死：左边的差是 nums[i] 减那个数、右边反过来，整段就能拆成两段普通求和。

左边那摊，这 i 个都比 nums[i] 小、差就是它减左数，它们的和记作前缀和 t，累加即 i×nums[i] − t。右边那摊，右侧 n−1−i 个数的和为后缀和，等于总和 s 减 t 再减 nums[i]，绝对差之和是它减去 n−1−i 个 nums[i]。相加就是 result[i]。

一遍扫描，前缀和边走边攒

落到代码是从左到右扫一遍。开扫前先求总和 s，前缀和 t 从 0 起步。每到下标 i，先用手头的 t——它正好是左侧那些数的和——算出 result[i]，然后才 t += nums[i]。先算后加的次序是死的，t 绝不能把 nums[i] 自己裹进去。

用 [1,4,6,8,10] 把五个下标滚一遍

总和 s=1+4+6+8+10=29，t 从 0 起。下标 0、值 1：左边没数左贡献 0，后缀和 28，右贡献 28−4×1=24，result[0]=24，t 变 1。下标 1、值 4：左贡献 1×4−1=3，后缀和 24，右贡献 24−3×4=12，result[1]=15，t 变 5。

下标 2、值 6：左贡献 2×6−5=7，后缀和 18，右贡献 18−2×6=6，result[2]=13，t 变 11。下标 3、值 8：左贡献 3×8−11=13，后缀和 10，右贡献 10−1×8=2，result[3]=15，t 变 19。下标 4、值 10：左贡献 4×10−19=21，右边没数右贡献 0，result[4]=21。最终 [24,15,13,15,21]。

线性时间背后，前缀和的时机和个数别数错

求总和与滚前缀和各一遍仍是 O(n)，比暴力 O(n²) 低一档；额外只用 s、t 两个变量，空间 O(1)，返回的 result 是必须交的输出不另计。

有两处最易手滑。前缀和更新若抢在算 result[i] 之前，t 会把 nums[i] 自己裹进去、左贡献多减一份，答案偏小，顺序永远先算后加。个数也要数准：左边 i 个、右边 n−1−i 个，当前元素两边都不算。边界不必特判：全相等时结果全 0，只有两个数时每个下标另一边贡献落 0。

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 ans

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:
    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;
    }
}