What is the time complexity of the Sum of Absolute Differences in a Sorted Array?

The time complexity is O(n), achieved by using prefix sums to avoid nested loops.

How do prefix sums help in solving the Sum of Absolute Differences problem?

Prefix sums allow for efficient summation of absolute differences by computing cumulative sums as you traverse the array.

How does the sorted property of the array help in solving the problem?

The sorted property allows for simplification of the absolute difference calculation, making it possible to calculate results in linear time.

What is a common mistake when solving this problem?

A common mistake is not taking advantage of the sorted array property, resulting in a solution with higher time complexity.

What are some variations of the Sum of Absolute Differences problem?

Variations include calculating squared differences instead of absolute differences or solving the problem for unsorted arrays.

#1685

Medium

auto_awesome数组·数学

LeetCode 题解工作台

有序数组中差绝对值之和

给你一个非递减有序整数数组 nums 。请你建立并返回一个整数数组 result ，它跟 nums 长度相同，且 result[i] 等于 nums[i] 与数组中所有其他元素差的绝对值之和。换句话说， result[i] 等于 sum(|nums[i]-nums[j]|) ，其中 0 且 …

数组数学前缀和

题目描述

给你一个 非递减 有序整数数组 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⁵
1 <= nums[i] <= nums[i + 1] <= 10⁴

lightbulb

解题思路

方法一：求和 + 枚举

我们先求出数组 $nums$ 所有元素的和，记为 $s$ ，用变量 $t$ 记录当前已经枚举过的元素之和。

接下来枚举 $nums[i]$ ，那么 $ans[i] = nums[i] \times i - t + s - t - nums[i] \times (n - i)$ ，然后我们更新 $t$ ，即 $t = t + nums[i]$ 。继续枚举下一个元素，直到枚举完所有元素。

时间复杂度 $O(n)$ ，其中 $n$ 为数组 $nums$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        ans = []
        s, t = sum(nums), 0
        for i, x in enumerate(nums):
            v = x * i - t + s - t - x * (len(nums) - i)
            ans.append(v)
            t += x
        return ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of how absolute differences work in sorted arrays.
question_mark
Check for familiarity with prefix sums and how they can optimize summation problems.
question_mark
Evaluate the candidate’s ability to optimize an otherwise brute-force solution.

warning

常见陷阱

外企场景

error
Not leveraging the sorted array property, resulting in unnecessary nested loops.
error
Incorrect use of prefix sums or failure to update them correctly as the array is traversed.
error
Failing to optimize the solution for larger arrays, which may lead to time limit exceed errors.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Instead of absolute differences, calculate the sum of squared differences between each element and others.
arrow_right_alt
Consider cases where the array is not sorted, and the time complexity will increase.
arrow_right_alt
Calculate differences based on a dynamic range of indices rather than all elements in the array.

help

常见问题

外企场景

继续练习

#1588 所有奇数长度子数组的和 #1524 和为奇数的子数组数目 #1862 向下取整数对和