【数据结构-距离合】力扣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]

class Solution {
public:
    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
        int n = nums.size(),leftSum = 0,rightSum = accumulate(nums.begin(),nums.end(), 0);
        vector<int> result(n);
        for(int i = 0;i < n;i++){
            rightSum -= nums[i];
            result[i] = i * nums[i] - leftSum + rightSum - (n-1-i) * nums[i];
            leftSum += nums[i];
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

对于i的左边：
nums[i]必然大于左边的所有元素，所以可以数出左边的元素个数，即i个
result[i] = (nums[i] - nums[0]) + (nums[i] - nums[1]) + ......
                                        +(nums[i] - nums[i - 1])
合并后就为:
result[i] = i * nums[i] - (nums[0] + nums[1] + ... + nums[i - 1])
          = i * nums[i] - leftsum
1
2
3
4
5
6
7

以上代码来源：

由于题目给的数组是非递减的，经过数学变化，可以得到每个元素和其他元素的绝对值之和与该元素以及左边元素和及右边元素和之间的关系，进行计算即可。