1685. Sum of Absolute Differences in a Sorted Array
给你一个从小排到大的正整数阵列
回传新的阵列包含以下特性：
每个元素都是原本阵列减其他元素后取绝对值的总和
Input: nums = [2,3,5]
Output: [4,3,5]
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.
Input: nums = [1,4,6,8,10]
Output: [24,15,13,15,21]
Intuition:
把阵列列出来之后整理就能得到算法。
Approach:
我们把例题[2,3,5]的算法列出来并展开绝对值：
result[0] = |2-2| + |2-3| + |2-5| = 2-2 + 3-2 + 5-2
result[1] = |3-2| + |3-3| + |3-5| = 3-2 + 3-3 + 5-3
result[2] = |5-2| + |5-3| + |5-5| = 5-2 + 5-3 + 5-5
把计算重新整理
依阵列元素与自己分成两边：
2-2 + 3-2 + 5-2 = ( 2+3+5) - (2+2+2)
3-2 + 3-3 + 5-3 = (-2+3+5) - (3+3-3)
5-2 + 5-3 + 5-5 = (-2-3+5) - (5-5-5)
这样我们就能看出规律
变化分成两个部分：
1.左半边:初始是总和 每次会减少前一个计算的元素的两倍
2.右半边:初始是元素数量 每次会-2
( 2+3+5) - (2+2+2) = (( 2+3+5)) - 2* 3
(-2+3+5) - (3+3-3) = (( 2+3+5)-2*2) - 3* 1
(-2-3+5) - (5-5-5) = ((-2+3+5)-3*2) - 5*(-1)
根据上面找到的规律去计算就是答案
题目已经排序过输入进来的阵列
所以直接跑循环就好
TS Code:
function getSumAbsoluteDifferences (nums: number[]): number[] {
let result: number[] = []
let absSum = nums.reduce((p, c) => p + c, 0)
let elementCount = nums.length
for (let i = 0; i < nums.length; i++) {
const element = nums[i]
result.push(absSum - element * elementCount)
elementCount -= 2
absSum -= element * 2
}
return result
}

大师

这解法好猛喔