1685. Sum of Absolute Differences in a Sorted Array

# 1685. Sum of Absolute Differences in a Sorted Array#

## 题目 #

You are given an integer array `nums` sorted in non-decreasing order.

Build and return an integer array `result` with the same length as `nums` such that `result[i]` is equal to the summation of absolute differences between `nums[i]` and all the other elements in the array.

In other words, `result[i]` is equal to `sum(|nums[i]-nums[j]|)` where `0 <= j < nums.length` and `j != i` (0-indexed).

Example 1:

``````Input: nums = [2,3,5]
Output: [4,3,5]
Explanation: Assuming the arrays are 0-indexed, then
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.
``````

Example 2:

``````Input: nums = [1,4,6,8,10]
Output: [24,15,13,15,21]
``````

Constraints:

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

## 解题思路 #

• 利用前缀和思路解题。题目中说明了是有序数组，所以在计算绝对值的时候可以拆开绝对值符号。假设要计算当前 `result[i]`，以 `i` 为界，把原数组 `nums` 分成了 3 段。`nums[0 ~ i-1]``nums[i+1 ~ n]`，前面一段 `nums[0 ~ i-1]` 中的每个元素都比 `nums[i]` 小，拆掉绝对值以后，`sum(|nums[i]-nums[j]|) = nums[i] * i - prefixSum[0 ~ i-1]`，后面一段 `nums[i+1 ~ n]` 中的每个元素都比 `nums[i]` 大，拆掉绝对值以后，`sum(|nums[i]-nums[j]|) = prefixSum[i+1 ~ n] - nums[i] * (n - 1 - i)`。特殊的情况，`i = 0``i = n` 的情况特殊处理一下就行。

## 代码 #

``````package leetcode

//解法一 优化版 prefixSum + sufixSum
func getSumAbsoluteDifferences(nums []int) []int {
size := len(nums)
sufixSum := make([]int, size)
sufixSum[size-1] = nums[size-1]
for i := size - 2; i >= 0; i-- {
sufixSum[i] = sufixSum[i+1] + nums[i]
}
ans, preSum := make([]int, size), 0
for i := 0; i < size; i++ {
// 后面可以加到的值
res, sum := 0, sufixSum[i]-nums[i]
res += (sum - (size-i-1)*nums[i])
// 前面可以加到的值
res += (i*nums[i] - preSum)
ans[i] = res
preSum += nums[i]
}
return ans
}

// 解法二 prefixSum
func getSumAbsoluteDifferences1(nums []int) []int {
preSum, res, sum := []int{}, []int{}, nums[0]
preSum = append(preSum, nums[0])
for i := 1; i < len(nums); i++ {
sum += nums[i]
preSum = append(preSum, sum)
}
for i := 0; i < len(nums); i++ {
if i == 0 {
res = append(res, preSum[len(nums)-1]-preSum[0]-nums[i]*(len(nums)-1))
} else if i > 0 && i < len(nums)-1 {
res = append(res, preSum[len(nums)-1]-preSum[i]-preSum[i-1]+nums[i]*i-nums[i]*(len(nums)-1-i))
} else {
res = append(res, nums[i]*len(nums)-preSum[len(nums)-1])
}
}
return res
}
``````

Apr 8, 2023
Edit this page