# 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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
