链接：https://leetcode-cn.com/problems/sum-of-absolute-differences-in-a-sorted-array/
难度：medium
题目大概的意思很简单，就是求每个数字和其他所数字的相差的绝对值之和。乍一看是一个O(n*n)的题，但其实题目的关键是非递减数列。所以其实可以转换一下思路，拿原题的例子来做个解说。
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.
其实可以忽略本身与本身的差
当求result[0]的时候，可以转化为 (3 - 2) + (5 - 2) = (3 + 5) - 2 * 2 = sum[i+1..len] - nums[i] * (len - i)
当求result[1]的时候，可以转化为 (3 - 2) + (5 - 3) = nums[i] * (i - 1) - sum[0..i - 1] + sum[i+1 .. len] - nums[i] * (len - i)
所以问题就转化为求每个数字的前面数字的和sumBefore[len]以及后面数字的和sumAfter[len]. 这样时间和空间复杂度就控制在了 O(n)。
class Solution {
public int[] getSumAbsoluteDifferences(int[] nums) {
int[] sumBefore = new int[nums.length];
int[] sumAfter = new int [nums.length];
int[] result = new int [nums.length];
for (int i = 0; i < nums.length; i ++) {
if(i == 0) {
sumBefore[i] = 0;
sumAfter[nums.length - 1 - i] = 0;
} else {
sumBefore[i] = sumBefore[i - 1] + nums[i - 1];
sumAfter[nums.length - 1 - i] = sumAfter[nums.length - i] + nums[nums.length - i];
}
}
for(int i = 0; i < nums.length; i ++) {
result[i] = i * nums[i] - sumBefore[i] + sumAfter[i] - (nums.length - i - 1) * nums[i];
}
return result;
}
}
好久没做题，还是一次过，给自己点个赞～
执行用时：4 ms, 在所有 Java 提交中击败了60.78%的用户
内存消耗：49.8 MB, 在所有 Java 提交中击败了97.39%的用户
