leetcode 2121. 相同元素的间隔之和

 1 class Solution {
 2 public:
 3     const int N=1e5+5;
 4     vector<long long> getDistances(vector<int>& arr) {
 5         int n=arr.size();
 6         vector<int>v[N];
 7         vector<long long>ans(n,0);
 8         unordered_map<int,int>mp;
 9         for(int i=0;i)
10         {
11             v[arr[i]].push_back(i);
12             mp[arr[i]]=1;
13         }
14             
15         for(auto &[p,cnt]:mp)
16         {
17             long long ps=0;
18             for(int j=0;j)
19             {
20                 ps+=v[p][j];
21                 ans[v[p][j]]+=1ll*(j+1)*v[p][j]-ps;
22             }
23             ps=0;
24             for(int j=v[p].size()-1;j>=0;j--)
25             {
26                 ps+=v[p][j];
27                 ans[v[p][j]]+=ps-1ll*(v[p].size()-j)*v[p][j];
28             }
29         } 
30         return ans;
31     }
32 };