題目敘述
題目會給我們一個陣列nums，要求我們以每個陣列元素分別當作軸心點，計算差值的絕對值總和，最後以陣列的形式，返回答案。
測試範例
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 <= 1051 <= nums[i] <= nums[i + 1] <= 104
演算法
除了第一直覺的暴力雙層迴圈搜索之外，其實還有一個更高效率的線性掃描法。
在側邊欄中搜尋
對於當下軸心點nums[i]而言
題目所求
= abs( nums[i] - nums[0] ) + abs( nums[i] - nums[1] ) + ... + abs( nums[i] - nums[i-1] ) + abs( nums[i] - nums[i+1] ) + ... + abs( nums[i] - nums[n-1] )
= num[i] 對比較小的那一群數字的差值絕對值總和 +
num[i] 對比較大的那一群數字的差值絕對值總和
= abs { nums[i] * i - sum of smaller numbers } +
abs{ nums[i] * (n-1-i) - sum of larger numbers }
= nums[i] * i - sum of smaller numbers +
sum of larger numbers - nums[i] * (n-1-i)
我們可以用一個線性掃描，從左往右，每次迭代更新 比較小的那一群數字總和、比較大的那一群數字總和，計算整體的差值絕對值總和。
最終，以陣列的形式返回答案即可。
程式碼
class Solution:
def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
n = len(nums)
sum_below, sum_above = 0, sum(nums)
sum_abs_diff = []
# Iterate each number
for i, number in enumerate(nums):
# Sum of numbers smaller than nums[i]
sum_below += number
# Sum of absolute difference to smaller numbers
diff_sum_below = i * number - sum_below
# Sum of absolute difference to larger numbers
diff_sum_above = sum_above - (n-1-i) * number
sum_abs_diff.append( diff_sum_below + diff_sum_above )
# Sum of numbers larger than nums[i]
sum_above -= number
return sum_abs_diff
複雜度分析
時間複雜度: O(n)
線性掃描，從左到右掃描每個陣列元素，總共耗時O(n)
空間複雜度: O(1)
解答所使用的空間sum_abs_diff不包含在內。
剩下的都是固定尺存的臨時變數，為常數級別O(1)
關鍵知識點
從圖解，和歸納小規模的例子可以發現:
我們可以用一個線性掃描，從左往右，每次迭代更新 比較小的那一群數字總和、比較大的那一群數字總和，計算整體的差值絕對值總和。
Reference:
