1685. 有序数组中差绝对值之和.md

1685. 有序数组中差绝对值之和

• 数学 + 前缀和

function getSumAbsoluteDifferences(nums: number[]): number[] {

    const results: number[] = [],
        prefixSum: number[] = [],
        { length } = nums,
        sum: number = nums.reduce((total, value) => total + value, 0);

    for (let i = 0; i < length; ++i) {
        prefixSum[i] = (prefixSum[i - 1] || 0) + nums[i];
        results[i] = (2 * i - length) * nums[i] + sum - 2 * (prefixSum[i - 1] || 0);
    }

    return results;

};
// 公式推导:
// A[k] - A[0]
// A[k] - A[1]
// A[k] - A[2]
// ...
// A[k] - A[k - 1]
// A[k] - A[k]
// A[k + 1] - A[k]
// A[k + 2] - A[k]
// ...
// A[n - 1] - A[k]
// =
// (k + 1)A[k] - (n - k)A[k] + sum[k+1:n] - sum[0:k-1]
// (2k + 1 - n)A[k] + sum[k+1:n-1] - sum[0:k-1]
// =
// (2k + 1 - n)A[k] + sum[0:n-1] - sum[0:k-1] - A[k] - sum[0:k-1]
// =
// (2k + 1 - n)A[k] + sum[0:n-1] - 2 * sum[0:k-1] - A[k]
// =
// (2k - n)A[k] + sum[0:n-1] - 2 * sum[0:k-1]