LeetCode 2121. 相同元素的间隔之和（前缀和）

示例 1：
输入：arr = [2,1,3,1,2,3,3]
输出：[4,2,7,2,4,4,5]
解释：
- 下标 0 ：另一个 2 在下标 4 ，|0 - 4| = 4
- 下标 1 ：另一个 1 在下标 3 ，|1 - 3| = 2
- 下标 2 ：另两个 3 在下标 5 和 6 ，|2 - 5| + |2 - 6| = 7
- 下标 3 ：另一个 1 在下标 1 ，|3 - 1| = 2
- 下标 4 ：另一个 2 在下标 0 ，|4 - 0| = 4
- 下标 5 ：另两个 3 在下标 2 和 6 ，|5 - 2| + |5 - 6| = 4
- 下标 6 ：另两个 3 在下标 2 和 5 ，|6 - 2| + |6 - 5| = 5

示例 2：
输入：arr = [10,5,10,10]
输出：[5,0,3,4]
解释：
- 下标 0 ：另两个 10 在下标 2 和 3 ，|0 - 2| + |0 - 3| = 5
- 下标 1 ：只有这一个 5 在数组中，所以到相同元素的间隔之和是 0
- 下标 2 ：另两个 10 在下标 0 和 3 ，|2 - 0| + |2 - 3| = 3
- 下标 3 ：另两个 10 在下标 0 和 2 ，|3 - 0| + |3 - 2| = 4
 
提示：
n == arr.length
1 <= n <= 10^5
1 <= arr[i] <= 10^5

class Solution {
public:
    vector<long long> getDistances(vector<int>& arr) {
        unordered_map<int,vector<long long>> pos; //  相同数字的位置
        for(int i = 0; i < arr.size(); ++i)
            pos[arr[i]].push_back(i); // 数字的各个位置
        vector<long long> ans(arr.size(), 0);
        for(auto& p : pos)
        {
            vector<long long> pp = p.second;
            for(int i = 1; i < pp.size(); ++i)
                pp[i] += pp[i-1]; // 各个位置的前缀和
            int lnum = 0, rnum = p.second.size();
            for(int i = 0; i < p.second.size(); ++i)
            {
                lnum = i; // i 左边有的同数字的 个数
                rnum = p.second.size()-i-1; // 右侧有的个数
                long long idx = p.second[i]; // 对应原来数组中的位置
                ans[idx] = pp.back()-pp[i] - idx*rnum + idx*lnum - (i>0 ? pp[i-1] : 0);
                // a1,a2,... i, ... b1, b2 后半段的都可以拆成 b1-i, b2-i, 个数  rnum个
                // 前半段 都可以拆成 i-a1, i-a2,... 个数 lnum个
                // a1, a2, ... 的和用前缀和直接获取
                // b1, b2, ... 的和用前缀和做差获取
            }
        }
        return ans;
    }
};