鏈接：https://leetcode-cn.com/problems/sum-of-absolute-differences-in-a-sorted-array/
難度：medium

題目大概的意思很簡單，就是求每個(gè)數(shù)字和其他所數(shù)字的相差的絕對值之和。乍一看是一個(gè)O(n*n)的題，但其實(shí)題目的關(guān)鍵是非遞減數(shù)列。所以其實(shí)可以轉(zhuǎn)換一下思路，拿原題的例子來做個(gè)解說。

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.

其實(shí)可以忽略本身與本身的差
當(dāng)求result[0]的時(shí)候，可以轉(zhuǎn)化為 (3 - 2) + (5 - 2) = (3 + 5) - 2 * 2 = sum[i+1..len] - nums[i] * (len - i)
當(dāng)求result[1]的時(shí)候，可以轉(zhuǎn)化為 (3 - 2) + (5 - 3) = nums[i] * (i - 1) - sum[0..i - 1] + sum[i+1 .. len] - nums[i] * (len - i)

所以問題就轉(zhuǎn)化為求每個(gè)數(shù)字的前面數(shù)字的和sumBefore[len]以及后面數(shù)字的和sumAfter[len]. 這樣時(shí)間和空間復(fù)雜度就控制在了 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;
    }
}

好久沒做題，還是一次過，給自己點(diǎn)個(gè)贊～

執(zhí)行用時(shí)：4 ms, 在所有 Java 提交中擊敗了60.78%的用戶
內(nèi)存消耗：49.8 MB, 在所有 Java 提交中擊敗了97.39%的用戶