我的思路是既然阵列中排序在后者一定不小于前者，
不妨将答案中的每个元素都视为后者减去前者的总和，
并且把跨越超过一个元素的差值都分解，
以第二个题目范例(nums=[1,4,6,8,10])来说，
如果定义a = nums[1] - nums[0]，
且b = nums[2] - nums[1]并以此类推，
则原题目会变成
result[0] = 4a + 3b + 2c + d = 24
result[1] = a + 3b + 2c + d = 15
result[2] = a + 2b + 2c + d = 13
result[3] = a + 2b + 3c + d = 15
result[4] = a + 2b + 3d + 4d = 21
可观察到result[0]的值为每个差值乘以一个等差数列的总和，
并且result[1]相对于result[0]来说只少了3a的部分，
其他的答案之间也都是只变动一个元素，
所以就可以用O(n)的循环解决了
Python Code:
class Solution:
def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [0 for i in range(n)]
ans[0] = sum([(nums[i] - nums[i-1]) * (n-i) for i in range(1,n)])
for i in range(1,n):
ans[i] = ans[i-1] - (nums[i] - nums[i-1]) * (n-i*2)
return ans
C++ Code:
class Solution {
public:
vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
const int n = nums.size();
vector<int> ans(n,0);
for (int i = 1;i < n;i++){
ans[0] += (nums[i] - nums[i-1]) * (n-i);}
for (int i = 1;i < n;i++){
ans[i] = ans[i-1] - (nums[i] - nums[i-1]) * (n-i*2);}
return ans;
}
};
※ 引述《ZooseWu (动物园 公告)》之铭言：
: 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
: }

大师

大师

大师