# 2121. 相同元素的间隔之和
### 题目地址(5965. 相同元素的间隔之和)
### 题目描述
```
给你一个下标从 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.length
1 <= n <= 10^5
1 <= arr[i] <= 10^5
```
### 前置知识
* 前缀和
### 公司
* 暂无
### 思路
朴素的思路是 $n^2$ 的暴力枚举，即对于每一个索引 i ，暴力枚举其与数组所有其他索引的间隔，并将其全部加起来即可。
考虑到数据范围为 $10^5$， 因此上面的思路是不可行的，会超时。我们的思路是优化到至少 $nlogn$。这种数据规模要么优化到 $nlogn$ 要么就是 $n$。
如果优化到 $n$。对于这种题目容易想到的就是动态规划，单调栈，前缀和。
首先想到的思路是动态规划。对于每一个索引 i ，我们是否可以借助其他索引的**间隔和**得到答案。
答案是可以的！这里的其他索引具体来说其实是其他的和 arr\[i] 值相等的索引。 不难想到用 dp\[i] 表示子数组 arr\[:i] 中 i 的间隔和，最终答案就是 dp\[n-1]。
这是一个最初的想法。实际上还有需要细节需要处理。
* 首先， i 向前看的时候需要看的是和 arr\[i] 值相同的已处理好的答案。因此我们的 dp 定义少了一个维度。不妨用 dp\[i]\[x] 表示 子数组 arr\[:i] 且值为的 x 的 i 的间隔和，最终答案就是对于数组所有 x dp\[n-1]\[x] 求和。
* 其次，如果计算间隔和呢？上面的朴素的思路是对于 i ，枚举所有小于 i 的 j，如果 arr\[j] == arr\[i]， 则加入到间隔和。
* 如果优化上一步的计算呢？我们可以利用类似前缀和的技巧来计算。 其中 pre\[a] 表示上一次出现的 a 的间隔和。 那么 i 的间隔和就是 `(i - last)*cnt + pre[last]` ，其中 last 就是 a 的上一次出现的位置，cnt 是 i 的前面的 a 出现的次数。这提示我们除了维护前缀信息，也要维护 cnt 信息。 pre\[a] = (v, c) 表示上一个 a 的位置的前缀间隔和为 v，且前面和 a 相同的数字有 c 个。
对于每一个 i 仅按照上面的计算会漏掉 i 右侧部分的间隔和。因此我们可以使用相同的技巧，用一个后缀和来解决。
### 关键点
* 前缀和 + 后缀和优化时间复杂度
### 代码
* 语言支持：Python3
Python3 Code:
```python
class Solution:
def getDistances(self, arr: List[int]) -> List[int]:
ans = []
n = len(arr)
last_map = collections.defaultdict(lambda:-1)
pre = collections.defaultdict(lambda:(0,0))
suf = collections.defaultdict(lambda:(0,0))
for i in range(n):
a = arr[i]
last = last_map[a]
v, c = pre[last]
pre[i] = v + c * (i - last), c + 1
last_map[a] = i
last_map = collections.defaultdict(lambda:len(arr))
for i in range(n-1,-1,-1):
a = arr[i]
last = last_map[a]
v, c = suf[last]
suf[i] = v + c * (last - i), c + 1
last_map[a] = i
for i, a in enumerate(arr):
ans.append(pre[i][0] + suf[i][0])
return ans
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：我们遍历了两次数组，因此时间复杂度为 $O(n)$
* 空间复杂度：pre 和 suf 以及 last\_map 都和数组不同数字的个数同阶，最差情况数组都是不同的，此时空间复杂度为 $O(n)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/5965.intervals-between-identical-elements.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.