What is the main pattern behind solving the Sum of Distances problem?

The problem revolves around scanning the array and using hash tables for efficient index lookup and distance calculation. Optimizations like prefix sums can further enhance performance.

How can I optimize the Sum of Distances problem?

Using a hash table to store indices for repeated elements and applying a prefix sum technique for running totals can significantly optimize the solution.

What is the time complexity of the Sum of Distances problem?

The time complexity is generally O(n), where n is the length of the input array, especially with optimized techniques like prefix sums and hash lookups.

What should I avoid when solving the Sum of Distances problem?

Avoid using nested loops or recalculating distances multiple times, which can lead to inefficient solutions.

Can I use prefix sums for the Sum of Distances problem?

Yes, prefix sums can be used to optimize the solution by maintaining running totals of indices for faster distance calculations.

#2615

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

等值距离和

给你一个下标从 0 开始的整数数组 nums 。现有一个长度等于 nums.length 的数组 arr 。对于满足 nums[j] == nums[i] 且 j != i 的所有 j ， arr[i] 等于所有 |i - j| 之和。如果不存在这样的 j ，则令 arr[i] 等于 0 。返回数…

数组哈希表前缀和

题目描述

给你一个下标从 0 开始的整数数组 nums 。现有一个长度等于 nums.length 的数组 arr 。对于满足 nums[j] == nums[i] 且 j != i 的所有 j ，arr[i] 等于所有 |i - j| 之和。如果不存在这样的 j ，则令 arr[i] 等于 0 。

返回数组 arr 。

示例 1：

输入：nums = [1,3,1,1,2]
输出：[5,0,3,4,0]
解释：
i = 0 ，nums[0] == nums[2] 且 nums[0] == nums[3] 。因此，arr[0] = |0 - 2| + |0 - 3| = 5 。 
i = 1 ，arr[1] = 0 因为不存在值等于 3 的其他下标。
i = 2 ，nums[2] == nums[0] 且 nums[2] == nums[3] 。因此，arr[2] = |2 - 0| + |2 - 3| = 3 。
i = 3 ，nums[3] == nums[0] 且 nums[3] == nums[2] 。因此，arr[3] = |3 - 0| + |3 - 2| = 4 。 
i = 4 ，arr[4] = 0 因为不存在值等于 2 的其他下标。

示例 2：

输入：nums = [0,5,3]
输出：[0,0,0]
解释：因为 nums 中的元素互不相同，对于所有 i ，都有 arr[i] = 0 。

提示：

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：哈希表 + 前缀和

我们先用哈希表 $d$ 记录数组 $nums$ 中每个元素对应的下标列表，即 $d[x]$ 表示数组 $nums$ 中所有值为 $x$ 的下标列表。

对于哈希表 $d$ 中的每个值列表 $idx$ ，我们可以计算出 $idx$ 中每个下标 $i$ 对应的 $arr[i]$ 的值。对于第一个下标 $idx[0]$ ，右边所有下标距离 $idx[0]$ 的和 $right=\sum_{i=0}^{m-1} - idx[0] \times m$ 。接下来我们遍历 $idx$ ，每一次计算得到 $ans[idx[i]] = left + right$ ，然后更新 $left$ 和 $right$ ，即 $left = left + (idx[i+1] - idx[i]) \times (i+1)$ ，而 $right = right - (idx[i+1] - idx[i]) \times (m-i-1)$ 。

遍历结束后，我们得到了数组 $nums$ 中每个元素对应的 $arr$ 的值，即 $ans$ 。

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def distance(self, nums: List[int]) -> List[int]:
        d = defaultdict(list)
        for i, x in enumerate(nums):
            d[x].append(i)
        ans = [0] * len(nums)
        for idx in d.values():
            left, right = 0, sum(idx) - len(idx) * idx[0]
            for i in range(len(idx)):
                ans[idx[i]] = left + right
                if i + 1 < len(idx):
                    left += (idx[i + 1] - idx[i]) * (i + 1)
                    right -= (idx[i + 1] - idx[i]) * (len(idx) - i - 1)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates an understanding of using hash tables for efficient lookups.
question_mark
The candidate considers optimizing the solution with prefix sums, showing awareness of performance constraints.
question_mark
The candidate clearly explains the relationship between array scanning and hash lookup in this problem.

warning

常见陷阱

外企场景

error
Overcomplicating the problem with unnecessary nested loops or recalculating distances multiple times.
error
Not leveraging the power of hash tables for fast index lookups, which can lead to inefficient solutions.
error
Failing to recognize the value of using a prefix sum approach, resulting in suboptimal performance for large arrays.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to consider different types of distance metrics, such as squared differences.
arrow_right_alt
Instead of summing distances, return the maximum distance for each element's repeated occurrences.
arrow_right_alt
Extend the problem to handle multidimensional arrays where the comparison of elements occurs across multiple axes.

help

常见问题

外企场景

继续练习

#2588 统计美丽子数组数目 #2488 统计中位数为 K 的子数组 #2845 统计趣味子数组的数目