力扣2615. 等值距离和

由数据范围是10^5，只能一次遍历，暴力是别想了，
看到arr[i] 等于所有 |i - j| 之和，这很明显是求距离和的方法—数学公式推导+前缀和
下面这一题也有类似的思路

1685. 有序数组中差绝对值之和

那我们如何处理满足 nums[j] == nums[i] 且 j != i 的所有 j这个条件呢？
我们可以用哈希表来存储，对于相同元素的值的下标/索引，我们可以选择把它存在一一个数组里面
也就是

unordered_map<int,vector<int>> mp; for(int i=0;i<nums.size();i++) { mp[nums[i]].push_back(i); }

这样具有相同的值的下标就到一个数组里面了！
然后，
我们可以取哈希表中的key值
得到一个索引数组（就是上文提到的对于相同元素的值的下标/索引，我们可以选择把它存在一一个数组里面）
我们只需要对这个数组中的每一个元素求一下 |i - j| 之和也就是sum(abs(i-j))
我们已知了装有i，j的数组（索引数组）那求起来就很好求
只需要对sum(abs(i-j))展开
因为带有绝对值，所以我们分成两部分
（这里就是把式子展开，具体可以自己列列式子和合并同类项）

sumleft和sumright sumleft=index*i-sum[i] sumright=(sum[a.size()]-sum[i+1])-index*(a.size()-(i+1)); sum=sumleft+sumright;

这样我们就求出了一个索引i它的sum(abs(i-j))的值
也就是题目中arr数组中的一个元素。
因此我们就可以写代码了

class Solution { public: long long sum[100005]; unordered_map<int,vector<int>> mp; vector<long long> distance(vector<int>& nums) { for(int i=0;i<nums.size();i++) { mp[nums[i]].push_back(i); } vector<long long> result(nums.size()); for(auto q:mp) { vector<int> a=q.second; for(int i=0;i<a.size();i++) { sum[i+1]=sum[i]+a[i]; } for(int i=0;i<a.size();i++) { int index=a[i]; long long sumleft=(long long)index*i-sum[i]; long long sumright=(sum[a.size()]-sum[i+1])-(long long)index*(a.size()-(i+1)); long long sum=sumleft+sumright; result[index]=sum; } } return result; } };

需要注意的是要开long long ，不仅是前缀和需要开long long ，在算sumleft和sunright的过程中遇到乘法的时候也需要开long long，这一点不得不防。
时间复杂度O(n)
这里是双重循环，但不代表是O（n^2)因为每次从哈希表中取数据是O（1）。