# 2121. Intervals Between Identical Elements
###### tags: `Leetcode` `Medium` `Prefix Sum`
Link: https://leetcode.com/problems/intervals-between-identical-elements/description/
## 思路
先用map收集每个element出现的所有index
然后分两段计算interval

假设```arr[i]==arr[j]```(```i<j```)
那么```prefix[j] = prefix[i]+(j左边的identical elements的个数)*(j-i)```

## Code

class Solution {
public long[] getDistances(int[] arr) {
int n = arr.length;
long[] ans = new long[n];
Map<Integer, List<Integer>> map = new HashMap<>();
for(int i=0; i<n; i++){
if(!map.containsKey(arr[i])){
map.put(arr[i], new ArrayList<>());
}
map.get(arr[i]).add(i);
}

long[] prefix = new long[n];
long[] postfix = new long[n];
for(int key:map.keySet()){
List<Integer> list = map.get(key);
for(int i=1; i<list.size(); i++){
prefix[list.get(i)] = prefix[list.get(i-1)]+i*(long)(list.get(i)-list.get(i-1));
}
}
for(int key:map.keySet()){
List<Integer> list = map.get(key);
for(int i=list.size()-2; i>=0; i--){
postfix[list.get(i)] = postfix[list.get(i+1)]+(long)(list.size()-i-1)*(long)(list.get(i+1)-list.get(i));
}
}
for(int i=0; i<n; i++){
ans[i] = postfix[i]+prefix[i];
}
return ans;
}
}