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

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        total_sum = 0
        prefix_sum = [0] * len(nums)
        
        # 计算前缀和
        for i in range(len(nums)):
            total_sum += nums[i]
            prefix_sum[i] = total_sum
        
        # 计算每个数的差绝对值之和
        output = [0] * len(nums)
        for i in range(len(nums)):
            sum_of_left_differences = (i + 1) * nums[i] - prefix_sum[i]
            sum_of_right_differences = prefix_sum[-1] - prefix_sum[i] - nums[i] * (len(nums) - 1 - i)
            output[i] = sum_of_left_differences + sum_of_right_differences
        
        return output

解题思路

因为数组是有序的, 对数任意一个数nums[i],

在数nums[i]左边的数比nums[i]小, 在nums[i]右边的数比nums[i]大,

因此, 计算nums[i]和其他数的差绝对值之和可以分割为两部分来进行计算.

首先计算前缀和数组prefixSum[], prefixSum[i]表示前i个数之和.

对于nums[i]的左半部分, nums[i]与其他数的差绝对值之和可计算为:

sumOfLeftDifferences = (i+1)*nums[i]-prefixSum[i];

对于nums[i]的右半部分, nums[i]与其他数的绝对值之和可计算为:

sumOfRightDifferences = prefixSum[nums.length-1]-prefixSum[i]-nums[i]*(nums.length-1-i);

所以, 当前nums[i]与左右其他数的绝对值之和为:

sumOfDifferences = sumOfLeftDifferences+sumOfRightDifferences;

• 在循环中，首先计算了整个列表的总和，并用prefix_sum列表保存了前缀和。
• 然后，在第二个循环中，针对每个元素，计算了其左边和右边所有元素的差的绝对值之和。
• 最后，将每个元素的左边差绝对值之和和右边差绝对值之和相加，得到了最终的结果列表output。

这段代码的目的是计算每个数的差的绝对值之和，并返回一个列表，其中每个元素是对应位置数的差的绝对值之和。