[数据结构与算法]LeetCode 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

题目链接：https://leetcode.com/problems/sum-of-absolute-differences-in-a-sorted-array/

题目大意：求每个元素和其他元素差的绝对值的和

题目分析：由于数组单调不减，第i位(0 based)的答案可以推出是

左边：sum[i]?- (i + 1) * nums[i]

右边：sum[n - 1] - sum[i - 1] - (n - i) * nums[i]?

之和，因此求出前缀和即可O(1)算出每个答案

5ms，时间击败69%

class Solution {
    public int[] getSumAbsoluteDifferences(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        int[] sum = new int[n];
        sum[0] = nums[0];
        for (int i = 1; i < n; i++) {
            sum[i] = sum[i - 1] + nums[i];
        }
        ans[0] = sum[n - 1] - n * nums[0];
        for (int i = 1; i < n; i++) {
            ans[i] = sum[n - 1] - sum[i - 1] - (n - i) * nums[i] + nums[i] * (i + 1) - sum[i];
        }
        return ans;
    }
}