一 前缀和
2615. 等值距离和 - 力扣（LeetCode）
在这个题目当中, 在考虑到使用一个 unordered_map<int, vector<int>> 储存相同数字的下标之后, 问题就变成了: 给定一个有序数组(这道题目当中存入 vector 的是下标, 在插入的时候自然就是有序的, 无需排序), 求这个数组中的一个数与其他所有数的差的绝对值之和, 这一点可以使用前缀和来解决, 用 s[i] 来表示数组 a 中的前 i 个数之和
前缀和中 s[] 的下标要从 1 开始, 如果 a[] 的下标也是从 1 开始的话, 就会配合默契, 但是如果说 a[] 的下标为 0 开始, 那么就用循环 i 依然从 1 开始, 但是用 a[i-1]
class Solution { public: typedef long long LL; vector<long long> distance(vector<int>& nums) { unordered_map<int, vector<int>> mp; int n=nums.size(); for(int i=0;i<n;i++){ mp[nums[i]].push_back(i); } vector<LL> arr(n); // 写成匿名函数可以更方便的使用 distance 中的局部变量 auto get_one=[&](vector<int>& vec){ int len_vec=vec.size(); vector<LL> s(len_vec+1); s[0]=0; // a 的下标是从 0 开始的 for(int i=0;i<len_vec;i++){ s[i+1]=s[i]+vec[i]; } // vec 的下标是从 0 开始的, 但是循环的时候 i 依然从 1 开始, 只是使用 vec[i-1] for(int i=1;i<=len_vec;i++){ LL l=1LL*i*vec[i-1]-s[i]; LL r=(s[len_vec]-s[i])-1LL*vec[i-1]*(len_vec-i); arr[vec[i-1]]=l+r; } }; for(auto it:mp){ get_one(it.second); } return arr; } };
