前缀和题目：有序数组中差绝对值之和

题目

标题和出处

标题：有序数组中差绝对值之和

出处：1685. 有序数组中差绝对值之和

难度

6 级

题目描述

要求

给定一个非递减有序整数数组 $\text{nums}$。

建立并返回一个整数数组 $\text{result}$，要求和 $\text{nums}$ 长度相同，且 $\text{result[i]}$ 等于 $\text{nums[i]}$ 与数组中所有其他元素差的绝对值之和。

换言之，$\text{result[i]}$ 等于 $\text{sum(|nums[i]-nums[j]|)}$，其中 $\text{0}\le \text{j}<\text{nums.length}$ 且 $\text{j}\ne \text{i}$（下标从 $\text{0}$ 开始）。

示例

示例 1：

输入：$\text{nums = [2,3,5]}$
输出：$\text{[4,3,5]}$
解释：假设数组下标从 $\text{0}$ 开始，那么
$\text{result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4}$，
$\text{result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3}$，
$\text{result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5}$。

示例 2：

输入：$\text{nums = [1,4,6,8,10]}$
输出：$\text{[24,15,13,15,21]}$

数据范围

• $\text{2}\le \text{nums.length}\le {\text{10}}^{\text{5}}$
• $\text{1}\le \text{nums[i]}\le \text{nums[i + 1]}\le {\text{10}}^{\text{4}}$

解法

思路和算法

由于数组 $\text{nums}$ 按非递减顺序排序，因此数组中的任意两个元素的差的绝对值等于后面的元素减前面的元素（即下标大的元素减下标小的元素）。当计算 $\text{result}[i]$ 时，对于每个下标 $j$，当 $j<i$ 时将 $\text{nums}[i]-\text{nums}[j]$ 加到 $\text{result}[i]$，当 $j>i$ 时将 $\text{nums}[j]-\text{nums}[i]$ 加到 $\text{result}[i]$。

当 $j=i$ 时，$\text{nums}[j]-\text{nums}[i]=0$，将 $\text{nums}[j]-\text{nums}[i]$ 加到 $\text{result}[i]$ 不会影响结果。为了方便处理，$j=i$ 的情况与 $j>i$ 的情况可以合并，即当 $j\ge i$ 时将 $\text{nums}[j]-\text{nums}[i]$ 加到 $\text{result}[i]$。

用 $n$ 表示数组 $\text{nums}$ 的长度，则 $\text{result}[i]$ 计算如下：

$$\begin{array}{rl}& \text{result}[i]\\ =& \sum _{j=0}^{i-1}(\text{nums}[i]-\text{nums}[j])+\sum _{j=i}^{n-1}(\text{nums}[j]-\text{nums}[i])\\ =& (\sum _{j=i}^{n-1}\text{nums}[j]-\sum _{j=0}^{i-1}\text{nums}[j])+(\sum _{j=0}^{i-1}\text{nums}[i]-\sum _{j=i}^{n-1}\text{nums}[i])\\ =& (\sum _{j=i}^{n-1}\text{nums}[j]-\sum _{j=0}^{i-1}\text{nums}[j])+\text{nums}[i]\times (2\times i-n)\end{array}$$

令 $\text{leftSum}[i]=\sum _{j=0}^{i-1}\text{nums}[j]$，$\text{rightSum}[i]=\sum _{j=i}^{n-1}\text{nums}[j]$，则有 $\text{result}[i]=(\text{rightSum}[i]-\text{leftSum}[i])+\text{nums}[i]\times (2\times i-n)$。其中，$\text{leftSum}[i]$ 为数组 $\text{nums}$ 的前 $i$ 个元素的前缀和，$\text{rightSum}[i]$ 为数组 $\text{nums}$ 的后 $n-i$ 个元素之和，可以在遍历数组 $\text{nums}$ 的过程中计算 $\text{leftSum}[i]$ 和 $\text{rightSum}[i]$ 的值。

实现方面，可以维护两个变量 $\text{leftSum}$ 和 $\text{rightSum}$，初始时 $\text{leftSum}=0$，$\text{rightSum}$ 为数组 $\text{nums}$ 的全部元素之和，在遍历数组 $\text{nums}$ 的过程中更新两个变量的值。

从左到右遍历数组 $\text{nums}$，对于下标 $i$，执行如下操作。

1. 计算 $\text{result}[i]=(\text{rightSum}-\text{leftSum})+\text{nums}\times (2\times i-n)$。

2. 将 $\text{leftSum}$ 增加 $\text{nums}[i]$，将 $\text{rightSum}$ 减少 $\text{nums}[i]$。

遍历结束之后即可得到结果数组 $\text{result}$。

代码

class Solution {
    public int[] getSumAbsoluteDifferences(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        int leftSum = 0, rightSum = 0;
        for (int i = 0; i < n; i++) {
            rightSum += nums[i];
        }
        for (int i = 0; i < n; i++) {
            result[i] = rightSum - leftSum + nums[i] * (2 * i - n);
            leftSum += nums[i];
            rightSum -= nums[i];
        }
        return result;
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\text{nums}$ 的长度。计算前缀和与计算答案数组各需要遍历数组 $\text{nums}$ 一次。

• 空间复杂度：$O(1)$。注意返回值不计入空间复杂度。