題目

給你一個 非遞減 有序整數陣列 nums 。

請你建立並返回一個整數陣列 result，它跟 nums 長度相同，

且result[i] 等於 nums[i] 與陣列中所有其他元素差的絕對值之和。

換句話說， result[i] 等於 sum(|nums[i]-nums[j]|) ，

其中 0 <= j < nums.length 且 j != i （下標從 0 開始）。

示例 1：輸入：nums = [2,3,5] 輸出：[4,3,5]

解釋：假設陣列下標從 0 開始，那麼

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。

示例 2：輸入：nums = [1,4,6,8,10] 輸出：[24,15,13,15,21]

提示：2 <= nums.length <= 105

1 <= nums[i] <= nums[i + 1] <= 104

解題思路分析

1、遍歷；時間複雜度O(n)，空間複雜度O(n)

func getSumAbsoluteDifferences(nums []int) []int {	n := len(nums)	res := make([]int, 0)	right := 0 // 右邊和	left := 0  // 左邊和	for i := 1; i < n; i++ {		right = right + (nums[i] - nums[0])	}	res = append(res, right)	for i := 1; i < n; i++ {		diff := nums[i] - nums[i-1]		left = left + diff*i		right = right - diff*(n-i)		res = append(res, left+right)	}	return res}

2、字首和；時間複雜度O(n)，空間複雜度O(n)

func getSumAbsoluteDifferences(nums []int) []int {	n := len(nums)	res := make([]int, 0)	arr := make([]int, 0)	sum := 0	for i := 0; i < n; i++ {		sum = sum + nums[i]		arr = append(arr, sum)	}	res = append(res, sum-n*nums[0])	for i := 1; i < n; i++ {		left := nums[i]*i - arr[i-1]              // 左邊和		right := (sum - arr[i]) - nums[i]*(n-1-i) // 右邊和		res = append(res, left+right)	}	return res}

總結

Medium題目，資料量10^5，暴力法容易超時，分別求左邊和右邊的和，然後加起來即可