由数据范围是10^5只能一次遍历暴力是别想了看到arr[i] 等于所有 |i - j| 之和这很明显是求距离和的方法—数学公式推导前缀和下面这一题也有类似的思路1685. 有序数组中差绝对值之和那我们如何处理满足 nums[j] nums[i] 且 j ! i 的所有 j这个条件呢我们可以用哈希表来存储对于相同元素的值的下标/索引我们可以选择把它存在一一个数组里面也就是unordered_mapint,vectorint mp; for(int i0;inums.size();i) { mp[nums[i]].push_back(i); }这样具有相同的值的下标就到一个数组里面了然后我们可以取哈希表中的key值得到一个索引数组就是上文提到的对于相同元素的值的下标/索引我们可以选择把它存在一一个数组里面我们只需要对这个数组中的每一个元素求一下 |i - j| 之和也就是sum(abs(i-j))我们已知了装有ij的数组索引数组那求起来就很好求只需要对sum(abs(i-j))展开因为带有绝对值所以我们分成两部分这里就是把式子展开具体可以自己列列式子和合并同类项sumleft和sumright sumleftindex*i-sum[i] sumright(sum[a.size()]-sum[i1])-index*(a.size()-(i1)); sumsumleftsumright;这样我们就求出了一个索引i它的sum(abs(i-j))的值也就是题目中arr数组中的一个元素。因此我们就可以写代码了class Solution { public: long long sum[100005]; unordered_mapint,vectorint mp; vectorlong long distance(vectorint nums) { for(int i0;inums.size();i) { mp[nums[i]].push_back(i); } vectorlong long result(nums.size()); for(auto q:mp) { vectorint aq.second; for(int i0;ia.size();i) { sum[i1]sum[i]a[i]; } for(int i0;ia.size();i) { int indexa[i]; long long sumleft(long long)index*i-sum[i]; long long sumright(sum[a.size()]-sum[i1])-(long long)index*(a.size()-(i1)); long long sumsumleftsumright; result[index]sum; } } return result; } };需要注意的是要开long long 不仅是前缀和需要开long long 在算sumleft和sunright的过程中遇到乘法的时候也需要开long long这一点不得不防。时间复杂度O(n)这里是双重循环但不代表是On^2)因为每次从哈希表中取数据是O1。