LeetCode 题解工作台
相同元素的间隔之和
给你一个下标从 0 开始、由 n 个整数组成的数组 arr 。 arr 中两个元素的 间隔 定义为它们下标之间的 绝对差 。更正式地， arr[i] 和 arr[j] 之间的间隔是 |i - j| 。 返回一个长度为 n 的数组 intervals ，其中 intervals[i] 是 arr[i]…
3
题型
4
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
class Solution: def getDistances(self, arr: List[int]) -> List[int]:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个下标从 0 开始、由 n 个整数组成的数组 arr 。
arr 中两个元素的 间隔 定义为它们下标之间的 绝对差 。更正式地，arr[i] 和 arr[j] 之间的间隔是 |i - j| 。
返回一个长度为 n 的数组 intervals ，其中 intervals[i] 是 arr[i] 和 arr 中每个相同元素（与 arr[i] 的值相同）的 间隔之和 。
注意：|x| 是 x 的绝对值。
示例 1：
输入：arr = [2,1,3,1,2,3,3] 输出：[4,2,7,2,4,4,5] 解释： - 下标 0 ：另一个 2 在下标 4 ，|0 - 4| = 4 - 下标 1 ：另一个 1 在下标 3 ，|1 - 3| = 2 - 下标 2 ：另两个 3 在下标 5 和 6 ，|2 - 5| + |2 - 6| = 7 - 下标 3 ：另一个 1 在下标 1 ，|3 - 1| = 2 - 下标 4 ：另一个 2 在下标 0 ，|4 - 0| = 4 - 下标 5 ：另两个 3 在下标 2 和 6 ，|5 - 2| + |5 - 6| = 4 - 下标 6 ：另两个 3 在下标 2 和 5 ，|6 - 2| + |6 - 5| = 5
示例 2：
输入：arr = [10,5,10,10] 输出：[5,0,3,4] 解释： - 下标 0 ：另两个 10 在下标 2 和 3 ，|0 - 2| + |0 - 3| = 5 - 下标 1 ：只有这一个 5 在数组中，所以到相同元素的间隔之和是 0 - 下标 2 ：另两个 10 在下标 0 和 3 ，|2 - 0| + |2 - 3| = 3 - 下标 3 ：另两个 10 在下标 0 和 2 ，|3 - 0| + |3 - 2| = 4
提示：
n == arr.length1 <= n <= 1051 <= arr[i] <= 105
解题思路
方法一
class Solution:
def getDistances(self, arr: List[int]) -> List[int]:
d = defaultdict(list)
n = len(arr)
for i, v in enumerate(arr):
d[v].append(i)
ans = [0] * n
for v in d.values():
m = len(v)
val = sum(v) - v[0] * m
for i, p in enumerate(v):
delta = v[i] - v[i - 1] if i >= 1 else 0
val += i * delta - (m - i) * delta
ans[p] = val
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for candidates who use a hash table to store indices for efficient interval calculation.
- question_mark
A good solution will show the candidate’s understanding of optimizing array scanning operations using hash tables.
- question_mark
Watch out for inefficient brute-force approaches that don’t scale with larger arrays.
常见陷阱
外企场景- error
Not properly handling cases where there are no other identical elements, leading to incorrect sum calculations.
- error
Using brute-force methods to compare each element with every other element, resulting in a time complexity of O(n^2).
- error
Not leveraging the hash table to efficiently look up the indices of identical elements, which significantly impacts performance.
进阶变体
外企场景- arrow_right_alt
Handling large arrays with more than one million elements.
- arrow_right_alt
Handling arrays with a small range of values or many repeated values.
- arrow_right_alt
Improving memory usage by optimizing how the indices are stored and accessed.