【Leetcode Daily】1685有序数组中差绝对值之和

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个数组，要求返回其中每一个值与其它所有元素差值的绝对值。

思路分享

• 前缀和的思路，可以参考 【Leetcode Daily】303区域和检索-数组不可变

• 从本题，可以学习到运用前缀和，简化一个数字与其左右两边数值之差值求解过程的方法。

  https://leetcode.cn/problems/sum-of-absolute-differences-in-a-sorted-array/solutions/3603710/ling-shen-ke-hou-qian-zhui-he-by-zhi-ma-2zjb3/

• 比如说，先以 0 为初始值求前缀和，那么每个数字对应的前缀和值，就相当于其左侧数字之和。

• 然后以当前遍历的数字为基准，分别求左侧数字个基准值与左侧数字之和的差值；

• 以及所有数字之和（最右边的前缀和）减去左侧数字之和得到的右侧数字之和，再减去右侧数字个基准值得到右侧数值的差值。

• 将上面的左右数值差值相加，就是一个数字与其它数值的差值之和了。

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        pre_sum = list(accumulate(nums, initial=0))
        n = len(nums)
        ans = []

        for i, x in enumerate(nums):
            left_sum = i*nums[i] - pre_sum[i]
            right_sum = pre_sum[n]-pre_sum[i] - (n-i)*nums[i]
            ans.append(left_sum + right_sum)
        
        return ans