Medium

题目描述

给你一个按 非递减顺序 排列的整数数组 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 <= 10^5
  • 1 <= nums[i] <= nums[i + 1] <= 10^4

解题思路

这道题的关键在于利用数组有序的性质来优化计算。

朴素解法：直接对每个位置计算与所有其他位置的绝对差之和，时间复杂度为 O(n²)，会超时。

优化思路：由于数组有序，对于位置 i，所有在其左边的元素都小于等于 nums[i]，右边的元素都大于等于 nums[i]。因此绝对差可以直接计算：

  • 左边部分：nums[i] - nums[j] (j < i)
  • 右边部分：nums[j] - nums[i] (j > i)

对于 result[i]，可以分解为：

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

进一步化简为：

result[i] = nums[i] * i - (nums[0] + ... + nums[i-1]) + (nums[i+1] + ... + nums[n-1]) - nums[i] * (n-i-1)

其中前缀和 prefix[i] 表示前 i 个元素的和，后缀和可以通过总和减去前缀和计算。这样每个位置只需要 O(1) 时间计算。

推荐解法：使用前缀和优化，时间复杂度 O(n)，空间复杂度 O(1)。

代码实现

class Solution {
public:
    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n);
        
        // 计算总和
        int total = 0;
        for (int num : nums) {
            total += num;
        }
        
        int prefix = 0;
        for (int i = 0; i < n; i++) {
            // 左边部分：nums[i] * i - prefix
            // 右边部分：(total - prefix - nums[i]) - nums[i] * (n - i - 1)
            result[i] = nums[i] * i - prefix + (total - prefix - nums[i]) - nums[i] * (n - i - 1);
            prefix += nums[i];
        }
        
        return result;
    }
};

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [0] * n
        
        # 计算总和
        total = sum(nums)
        
        prefix = 0
        for i in range(n):
            # 左边部分：nums[i] * i - prefix
            # 右边部分：(total - prefix - nums[i]) - nums[i] * (n - i - 1)
            result[i] = nums[i] * i - prefix + (total - prefix - nums[i]) - nums[i] * (n - i - 1)
            prefix += nums[i]
        
        return result

public class Solution {
    public int[] GetSumAbsoluteDifferences(int[] nums) {
        int n = nums.Length;
        int[] result = new int[n];
        
        // 计算总和
        int total = 0;
        foreach (int num in nums) {
            total += num;
        }
        
        int prefix = 0;
        for (int i = 0; i < n; i++) {
            // 左边部分：nums[i] * i - prefix
            // 右边部分：(total - prefix - nums[i]) - nums[i] * (n - i - 1)
            result[i] = nums[i] * i - prefix + (total - prefix - nums[i]) - nums[i] * (n - i - 1);
            prefix += nums[i];
        }
        
        return result;
    }
}

var getSumAbsoluteDifferences = function(nums) {
    const n = nums.length;
    const result = new Array(n);
    
    // 计算总和
    const total = nums.reduce((sum, num) => sum + num, 0);
    
    let prefix = 0;
    for (let i = 0; i < n; i++) {
        // 左边部分：nums[i] * i - prefix
        // 右边部分：(total - prefix - nums[i]) - nums[i] * (n - i - 1)
        result[i] = nums[i] * i - prefix + (total - prefix - nums[i]) - nums[i] * (n - i - 1);
        prefix += nums[i];
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需遍历数组一次计算总和，再遍历一次计算结果
空间复杂度O(1)除了返回数组外，只使用常数额外空间