---
# System prepended metadata

title: 2121. Intervals Between Identical Elements
tags: [Leetcode, Prefix Sum, Medium]

---

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

假设```arr[i]==arr[j]```(```i<j```)
那么```prefix[j] = prefix[i]+(j左边的identical elements的个数)*(j-i)```
```postfix[i] = postfix[j]+(i右边的identical elements的个数)*(j-i)```
## Code
```java=
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;
    }
}
```