LeetCode 1685. 有序数组中差绝对值之和

约 4 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节
标签
数组 数学 前缀和

题目描述

✅ 1685. 有序数组中差绝对值之和

image-20260929090830186

题意分析

给定已经按非递减顺序排列的数组，对每个下标 i，计算 nums[i] 与所有数组元素的绝对差之和。数组可以有重复值，自身贡献为 0；要求一次求出所有位置的结果，避免对每个位置再扫描整个数组。

解法：前缀和分解贡献

核心思路

[!blue]
有序性让左右两侧的绝对值分别去掉。 对当前值 x=nums[i]，左侧所有元素都不大于它，所以左侧各项为 x-nums[j]。一共有 i 项，将相同的 x 合并，左侧贡献就是 x*i-leftSum。

右侧所有元素都不小于 x，各项为 nums[j]-x，一共有 n-1-i 项，所以右侧贡献为 rightSum-x*(n-1-i)。两侧与当前位置恰好覆盖整个数组，自身差值为 0，左右贡献相加就是答案。

用 prefix[i] 保存闭区间 nums[0..i] 的元素和。左侧不含当前项，因此 leftSum=prefix[i-1]；当 i=0 时左侧为空，取 0。右侧同样排除当前项，所以 rightSum=prefix[n-1]-prefix[i]。预处理后，每个位置只需常数次运算。

解题步骤

  1. 初始化 prefix[0]=nums[0]，随后按 prefix[i]=prefix[i-1]+nums[i] 累加。
  2. 对每个下标 i，取得不包含当前项的 leftSum 与 rightSum。
  3. 计算 nums[i]*i-leftSum 与 rightSum-nums[i]*(n-1-i)，相加后写入 res[i]。

第一个位置左侧的数量与和都为 0，最后一个位置右侧的数量与和都为 0，公式仍然成立。相等元素的差也自然抵消为 0，不需要额外去重或特殊分支。

代码实现

class Solution {
    public int[] getSumAbsoluteDifferences(int[] nums) {
        int n = nums.length;
        // 闭区间前缀和：prefix[i] = nums[0] + ... + nums[i]。
        long[] prefix = new long[n];

        prefix[0] = nums[0];

        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + nums[i];
        }

        int[] res = new int[n];

        for (int i = 0; i < n; i++) {
            long leftSum = 0;

            if (i > 0) {
                leftSum = prefix[i - 1];
            }

            // 减 prefix[i] 才能把 nums[i] 自身排除在右段之外。
            long rightSum = prefix[n - 1] - prefix[i];

            // 左侧有若干前项，右侧排除自身，数量必须与各自区间和对应。
            long left = (long) nums[i] * i - leftSum;
            long right = rightSum - (long) nums[i] * (n - 1 - i);

            res[i] = (int) (left + right);
        }

        return res;
    }
}

func getSumAbsoluteDifferences(nums []int) []int {
    n := len(nums)
    // 闭区间前缀和：prefix[i] = nums[0] + ... + nums[i]。
    prefix := make([]int, n)
    prefix[0] = nums[0]
    for i := 1; i < n; i++ {
        prefix[i] = prefix[i-1] + nums[i]
    }

    res := make([]int, n)
    for i := 0; i < n; i++ {
        leftSum := 0
        if i > 0 {
            leftSum = prefix[i-1]
        }
        // 减 prefix[i] 才能把 nums[i] 自身排除在右段之外。
        rightSum := prefix[n-1] - prefix[i]
        // 左侧有若干前项，右侧排除自身，数量必须与各自区间和对应。
        left := nums[i]*i - leftSum
        right := rightSum - nums[i]*(n-1-i)
        res[i] = left + right
    }
    return res
}

复杂度分析

  • 时间复杂度：$O(n)$，构造前缀和与计算答案各扫描一次。
  • 空间复杂度：$O(n)$，保存前缀和，结果另占 $O(n)$。

关键点总结

[!green]

  • 有序才能直接去掉绝对值符号。
  • 区间和与元素个数必须描述同一批元素。
  • 自身差值为零，无需额外减去自身的数值。

易错点总结

[!yellow]

  • 右侧和减 prefix[i-1]：包含当前值却没有同步增加数量，结果偏大。
  • i=0 时读取 prefix[-1]：访问越界，左侧为空时应取零。
  • 右侧数量使用 n-i：多计一个当前位置。
  • 混用两种前缀和定义：区间端点和总和位置都会错位。

相似题目

题目 难度 关联与区别
462. 最小操作次数使数组元素相等 II 中等 绝对距离和在中位数处最小，本题需要对每个给定位置求出这个距离和。
1480. 一维数组的动态和 简单 有序性确定绝对值符号后，前缀和能一次算出左右两侧的总差。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/11938646
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！