1685. Sum of Absolute Differences in a Sorted Array

題目描述

給定一個已排序的非遞減整數陣列 nums，回傳陣列 result，其中 result[i] 等於 nums[i] 與陣列中所有其他元素的絕對差之和：

result[i] = |nums[i] - nums[0]| + |nums[i] - nums[1]| + ... + |nums[i] - nums[n-1]|

解題思路

核心觀察：利用排序性質拆分絕對值

由於陣列已排序，對於位置 i：

• 左側元素（索引 0 到 i-1）都 ≤ nums[i]，所以 |nums[i] - nums[j]| = nums[i] - nums[j]（對 j < i）
• 右側元素（索引 i+1 到 n-1）都 ≥ nums[i]，所以 |nums[i] - nums[j]| = nums[j] - nums[i]（對 j > i）

因此：

result[i] = Σ(j<i) (nums[i] - nums[j])  +  Σ(j>i) (nums[j] - nums[i])
           = i * nums[i] - prefix[i]        +  (suffix[i] - (n-1-i) * nums[i])
           = i * nums[i] - prefix[i] + suffix[i] - (n-1-i) * nums[i]

其中：

• prefix[i] = nums[0] + nums[1] + ... + nums[i-1]（前 i 個元素的和，不含自身）
• suffix[i] = nums[i+1] + nums[i+2] + ... + nums[n-1]（後 n-1-i 個元素的和，不含自身）

前綴和計算

• prefix[i] = prefixSum[i]（可用前綴和陣列 O(1) 查詢）
• suffix[i] = totalSum - prefixSum[i+1]（用總和減去前綴和即得後綴和）

因此只需一個前綴和陣列，無需另建後綴和陣列。

時間複雜度

O(n)，其中 n 為陣列長度。

• 建立前綴和陣列：O(n)。
• 計算每個 result[i]：O(1)（利用前綴和）。
• 總計：O(n)。

若暴力計算每個 result[i]（雙重迴圈），時間 O(n²)；利用排序性質和前綴和可將複雜度降至最優 O(n)。

空間複雜度

O(n)，需要一個前綴和陣列（長度 n+1）。不計輸出陣列本身的話，也是 O(n)。若允許修改輸入或使用輸出陣列做前綴和，可降至 O(1) 額外空間。

替代方案

方案一：暴力雙重迴圈

對每個 i，用內層迴圈計算與所有其他元素的絕對差之和。

• 優點：邏輯最直觀，不需要任何推導。
• 缺點：時間 O(n²)，n=10^5 時需 10^10 操作，遠超時間限制。

方案二：排序 + 二分搜尋（未利用已排序）

若輸入陣列未排序，先排序（O(n log n)），然後對每個元素用二分搜尋找分界點，分別計算左右貢獻。

• 優點：適用於未排序的輸入。
• 缺點：本題輸入已排序，多此一舉；前綴和方案已是 O(n) 最優。

方案三：分別建立前綴和與後綴和陣列

顯式建立兩個陣列：prefix[i] = sum(nums[0..i-1]) 和 suffix[i] = sum(nums[i+1..n-1])。

• 優點：邏輯更直觀，兩個陣列分別對應左側貢獻和右側貢獻，易於理解和驗證。
• 缺點：需要額外的 O(n) 空間儲存後綴和陣列；但實際上後綴和 = totalSum - prefixSum[i+1]，無需額外陣列。本題的最優解只需一個前綴和陣列。

延伸問題

1. 未排序陣列的絕對差和：若輸入陣列未排序，先排序再計算前綴和，整體時間 O(n log n)，但回傳的 result 需要按原始索引排列，需記錄排序前的索引映射。

2. 加權絕對差：若每個位置有權重 w[i]，計算 result[i] = Σ w[j] * |nums[i] - nums[j]|（加權版本）。排序後同樣可以拆分絕對值，但需要在前綴和中同時累積 w[j] 和 w[j] * nums[j]，方法完全類比。

3. p 次方距離：若將絕對差替換為平方差（即 |nums[i] - nums[j]|²），利用展開式 (a-b)² = a² - 2ab + b²，可以類似地用前綴和計算。這是許多機器學習優化問題中的基礎技巧（如 k-means 的核心計算）。