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

给你一个 非递减 有序整数数组 nums 。

请你建立并返回一个整数数组 __result，它跟 __nums 长度相同，且result[i] 等于 __nums[i]
与数组中所有其他元素差的绝对值之和。

换句话说， result[i] 等于 sum(|nums[i]-nums[j]|) ，其中 0 <= j < nums.length 且 j != i （下标从 0 开始）。

示例 1：

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

示例 2：

**输入：** nums = [1,4,6,8,10]
**输出：** [24,15,13,15,21]

提示：

• 2 <= nums.length <= 105
• 1 <= nums[i] <= nums[i + 1] <= 104

解题思路

• 我们要计算 nums 数组中第 i 个数与其他数的绝对差值之和，可以将其拆分为三部分：

1. 与前面 i - 1 个数的绝对差值之和。
2. 与后面 n - i 个数的绝对差值之和。
3. 与自身的绝对差值（为 0）。

• 第 1 部分可以通过前缀和数组 pre 来计算
• 第 2 部分可以通过后缀和数组 last 来计算
• 第 3 部分就是自身与自身的差值。因此，我们可以遍历一遍 nums 数组，根据上述三部分计算出每个数与其他数的绝对差值之和，并将结果存放在 nums 数组中，最后返回 nums 数组即可。

代码详细注释及实现

class Solution {
public:
    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
        //定义前缀和数组和后缀和数组
        vector<int> pre(nums.size()), last(nums.size());
        //初始化前缀和数组和后缀和数组
        last[nums.size() - 1] = nums[nums.size() - 1], pre[0] = nums[0];
        //构造前缀和数组和后缀和数组
        for (int i = 1; i < nums.size(); ++i) pre[i] = nums[i] + pre[i - 1];
        for (int i = nums.size() - 2; i >= 0; --i) last[i] = nums[i] + last[i + 1];
        //进行求绝对值之和
        for (int i = 0; i < nums.size(); ++i) {
            //进行分情况考虑
            if (i == 0) nums[i] = last[i + 1] - nums[i]*(nums.size() - 1);
            else if (i == nums.size() - 1) nums[i] = nums[i]*(nums.size() - 1) - pre[i - 1];
            else nums[i] = i*nums[i] - pre[i - 1]  + last[i + 1] - (nums.size() - i - 1)*nums[i] ;
        }
        return nums;
    }
};