LeetCode 1685. 有序数组中差绝对值之和

2022-03-10 HGNULB 约 9 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 1685. 有序数组中差绝对值之和

题意分析

给一个非递减的整数数组 nums，对每个下标 i 求出它与其余所有元素之差的绝对值之和，返回这样一个等长数组。

题面里最重要的信息是「已经有序」。绝对值之所以难处理，是因为 $ a - b $ 要按大小关系分情况；而有序恰好把这个分类固定下来了——对于下标 i，所有 j < i 的元素都不大于它，所有 j > i 的元素都不小于它。于是绝对值可以直接去掉：左边那些贡献 $nums[i] - nums[j]$，右边那些贡献 $nums[j] - nums[i]$。

注意 j = i 这一项贡献 0，加不加都不影响结果，这给实现留了一点余地，但也是最容易算错的地方。

拆开之后每一侧都变成了「若干个 $nums[i]$ 减去（或加上）一段连续区间的元素和」，也就是说只要能 $O(1)$ 拿到任意前缀的和，每个下标的答案就能 $O(1)$ 算出来。这正是数据规模所要求的：n 最多 $10^5$，$O(n^2)$ 的两重循环会做 $10^{10}$ 次运算，必然超时。

数值范围上，元素不超过 $10^4$、个数不超过 $10^5$，所以总和的量级是 $10^9$，单个答案的量级同样是 $10^9$。这个值刚好在 32 位有符号整数的边缘，中间计算里出现 $nums[i] \times i$ 这样的乘积时必须留意类型。

边界包括：i = 0（左侧为空）；i = n - 1（右侧为空）；数组只有一个元素（答案为 0）；以及所有元素相等（答案全为 0）。

解法：前缀和分解贡献

核心思路

暴力做法是对每个 i 都扫一遍整个数组累加绝对值，$O(n^2)$。瓶颈在于同一段区间的和被反复重算——算 i 时用到 nums[0..i-1] 的和，算 i + 1 时又要用 nums[0..i] 的和，两者只差一项，却完全重头再来。

关键观察是有序性带来的符号固定：$\sum_j nums[i] - nums[j] $ 可以在下标 i 处一刀切开，左右两段各自去掉绝对值符号。左段有 i 个元素，每个都被 $nums[i]$ 减，所以左段贡献是 $nums[i] \cdot i - \sum_{j < i} nums[j]$；右段有 $n - 1 - i$ 个元素，每个都要减去 $nums[i]$，所以右段贡献是 $\sum_{j > i} nums[j] - nums[i] \cdot (n - 1 - i)$。

两段里唯一的未知量是「前 i 项之和」与「后 $n - 1 - i$ 项之和」，而后者等于总和减去前 i + 1 项之和。于是只需要一张前缀和表就够了。

定义 prefix[i] 为 $nums[0] + nums[1] + \dots + nums[i]$，即闭区间前缀和。那么左段和是 prefix[i - 1]（i = 0 时为 0），右段和是 prefix[n - 1] - prefix[i]。注意右段用的是 prefix[i] 而不是 prefix[i - 1]，因为要把 nums[i] 自己排除在右段之外——这一处下标差一是本题最高频的错误来源。

于是答案的闭式是 $res[i] = (nums[i] \cdot i - prefix[i-1]) + (prefix[n-1] - prefix[i] - nums[i] \cdot (n - 1 - i))$。前缀和一趟建好、结果一趟算出，整体线性。

顺带确认边界自洽：i = 0 时左段元素数为 0、左段和为 0，贡献恰好是 0；i = n - 1 时右段元素数为 0，且 prefix[n-1] - prefix[n-1] = 0，贡献同样是 0。两端都不需要特判。

解题步骤

先构造前缀和数组。prefix[0] = nums[0]，随后 prefix[i] = prefix[i-1] + nums[i]。选闭区间定义而不是「前 i 项」的开区间定义，是为了让 prefix[n-1] 直接就是总和，右段公式写起来更短；代价是取左段时要写 prefix[i-1] 并单独处理 i = 0。两种定义都可以，但必须全程只用一种。

先核对中间量上界。本题总和与答案都不超过约 $10^9$；Java 仍用 long 做前缀和与乘法以保留余量，Go 的 int 在 32 位和 64 位实现上都足以覆盖题目约束。

遍历每个下标 i，先取左段和：i > 0 时是 prefix[i-1]，否则是 0。这个判断不能省，否则会访问 prefix[-1]。

再取右段和 prefix[n-1] - prefix[i]。这里必须减 prefix[i] 而不是 prefix[i-1]，前者才把 nums[i] 自身排除掉；写错会让 nums[i] 被算进右段，右段贡献凭空多出一个 $nums[j] - nums[i] = 0$……实际后果是元素个数与和不匹配，结果偏大。

按公式算出左右贡献并相加写入结果。左段是「i 个 nums[i] 减去左段和」，右段是「右段和减去 $n - 1 - i$ 个 nums[i]」。两处的元素个数分别是 i 与 n - 1 - i，加起来正好是 n - 1，这是一个很好用的自检。

返回结果数组。

以 nums = [2, 3, 5] 走一遍，预期答案 [4, 3, 5]。

前缀和：prefix = [2, 5, 10]，总和 prefix[2] = 10。

i = 0：左段和为 0，左段贡献 $2 \times 0 - 0 = 0$；右段和 $10 - 2 = 8$，右段元素数 $3 - 1 - 0 = 2$，右段贡献 $8 - 2 \times 2 = 4$。合计 4。手工验证 $ 2-2 + 2-3 + 2-5 = 0 + 1 + 3 = 4$，一致。

i = 1：左段和 prefix[0] = 2，左段贡献 $3 \times 1 - 2 = 1$；右段和 $10 - 5 = 5$，右段元素数 $3 - 1 - 1 = 1$，右段贡献 $5 - 3 \times 1 = 2$。合计 3。手工验证 $ 3-2 + 0 + 3-5 = 1 + 2 = 3$，一致。

i = 2：左段和 prefix[1] = 5，左段贡献 $5 \times 2 - 5 = 5$；右段和 $10 - 10 = 0$，右段元素数 0，右段贡献 0。合计 5。手工验证 $ 5-2 + 5-3 + 0 = 3 + 2 = 5$，一致。

返回 [4, 3, 5]。若把右段和错写成 prefix[2] - prefix[i-1]，在 i = 1 处会得到 $10 - 2 = 8$，右段贡献变成 $8 - 3 = 5$，总和 6，答案错误——这正是那处下标差一造成的后果。

代码实现

class Solution {
    public int[] getSumAbsoluteDifferences(int[] nums) {
        int n = nums.length;
        // 闭区间前缀和：prefix[i] = nums[0] + ... + nums[i]。
        long[] prefix = new long[n];
        prefix[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + nums[i];
        }

        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            long leftSum = 0;
            if (i > 0) {
                leftSum = prefix[i - 1];
            }
            // 减 prefix[i] 才能把 nums[i] 自身排除在右段之外。
            long rightSum = prefix[n - 1] - prefix[i];

            long left = (long) nums[i] * i - leftSum;
            long right = rightSum - (long) nums[i] * (n - 1 - i);
            res[i] = (int) (left + right);
        }
        return res;
    }
}

func getSumAbsoluteDifferences(nums []int) []int {
	n := len(nums)
	// 闭区间前缀和：prefix[i] = nums[0] + ... + nums[i]。
	prefix := make([]int, n)
	prefix[0] = nums[0]
	for i := 1; i < n; i++ {
		prefix[i] = prefix[i-1] + nums[i]
	}

	res := make([]int, n)
	for i := 0; i < n; i++ {
		leftSum := 0
		if i > 0 {
			leftSum = prefix[i-1]
		}
		// 减 prefix[i] 才能把 nums[i] 自身排除在右段之外。
		rightSum := prefix[n-1] - prefix[i]
		left := nums[i]*i - leftSum
		right := rightSum - nums[i]*(n-1-i)
		res[i] = left + right
	}
	return res
}

复杂度分析

时间复杂度：$O(n)$。构造前缀和一趟、计算结果一趟，每个位置只做常数次乘加。相比暴力的 $O(n^2)$，节省来自「区间和不再重复累加」。

空间复杂度：$O(n)$，前缀和数组占 n 项。若不计返回值，可以把前缀和优化掉——只需在遍历中维护一个「已走过部分的和」，再用预先算好的总和相减，这样额外空间降到 $O(1)$。

关键点总结

「数组已排序」是去掉绝对值符号的许可证。看到绝对值先问「大小关系是否已知」，已知就立刻拆成两段无符号求和，这是处理绝对值求和的第一反应。

按贡献拆分是核心手法：把一个二重求和 $\sum_i \sum_j$ 拆成每个 i 独立可算的闭式。判断能否拆的标准是「固定 i 后，内层求和是否只依赖若干个区间统计量」。

前缀和的定义（闭区间还是开区间、要不要哨兵位）必须一开始就选定并全程贯彻。绝大多数错误不是公式推错，而是两种定义在同一段代码里混用。

左右两段的元素个数 i 与 n - 1 - i 加起来必须是 n - 1，这是一个成本极低的自检，能当场发现差一错误。

中间量要按约束估算，而不能假定 Go 的 int 固定为 64 位；本题上界适配 32 位，Java 代码使用 long 进一步避免扩展约束后的溢出风险。

面试视角：先说「有序 ⇒ 绝对值可去」，再当场推出左右两段的闭式，然后指出唯一未知量是区间和、引出前缀和。面试官常追问「如果数组无序怎么办」，答案是先排序再用同一套公式，但要注意输出需按原下标还原；再追问「能不能 $O(1)$ 空间」，回答是把前缀和换成滚动变量加总和相减即可。

易错点总结

错误写法：右段和写成 prefix[n-1] - prefix[i-1]。用例 nums = [2, 3, 5] → i = 1 处右段和算成 8，答案变成 6，正确答案是 3；nums[i] 被重复计入右段。

错误写法：左段和写成 prefix[i]。用例 nums = [2, 3, 5] → i = 1 处左段和算成 5，左段贡献变成 $3 - 5 = -2$，答案变成 0，正确答案是 3。

错误写法：i = 0 时不判断就取 prefix[i - 1]。用例 nums = [2, 3, 5] → 访问 prefix[-1]，Java 抛数组越界异常、Go 触发 panic。

错误写法：右段元素个数写成 n - i。用例 nums = [2, 3, 5] → i = 0 处右段贡献算成 $8 - 2 \times 3 = 2$，答案变成 2，正确答案是 4；nums[i] 自己被算进了右段的个数里。

错误写法：左段元素个数写成 i + 1。用例 nums = [2, 3, 5] → i = 2 处左段贡献算成 $5 \times 3 - 5 = 10$，答案变成 10，正确答案是 5。

错误写法：把前缀和定义成开区间 prefix[i] = nums[0] + ... + nums[i-1] 却仍用 prefix[n-1] 当总和。用例 nums = [2, 3, 5] → 总和取成 5 而不是 10，所有右段贡献都偏小，答案全错。

错误写法：认为 j = i 那一项必须显式排除，于是在结果里再减一次 nums[i]。用例 nums = [2, 3, 5] → i = 0 处答案变成 2，正确答案是 4；$ nums[i] - nums[i] = 0$，本来就不产生贡献。

错误写法：先对数组排序再计算。用例 nums = [2, 3, 5] → 结果不变，但题目已保证非递减，多余的排序把 $O(n)$ 拖成 $O(n \log n)$；若输入本就无序而又直接输出排序后的下标顺序，结果与原下标错位。

错误写法：用两重循环逐对累加绝对值。用例：$n = 10^5$ → 需要 $10^{10}$ 次运算，必然超时；思路正确但复杂度不过关。

相似题目

题目	难度	考察点
303. 区域和检索 - 数组不可变	简单	前缀和最纯粹的形态，考点只在预处理与区间查询的下标对应
724. 寻找数组的中心下标	简单	同样用「总和减前缀」得到后缀和，但目标是找平衡点而非逐位求值
238. 除了自身以外数组的乘积	中等	把前缀和换成前缀积，且要求 $O(1)$ 额外空间，展示同一思想的乘法版本
560. 和为 K 的子数组	中等	前缀和配哈希表做配对计数，重点从「逐位求值」转向「历史状态查询」
462. 最小操作次数使数组元素相等 II	中等	同样是绝对差之和，但要求最小化，答案落在中位数上，考点是数学结论
1109. 航班预订统计	中等	差分数组是前缀和的逆运算，用于区间修改后一次性还原
1314. 矩阵区域和	中等	前缀和升到二维，区间查询要用容斥四项相加减，下标处理更易出错
1200. 最小绝对差	简单	同样利用有序性处理绝对差，但只需比较相邻元素，无需任何区间统计