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

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

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

给你一个下标从 0 开始、由 n 个整数组成的数组 arr 。

arr 中两个元素的 间隔 定义为它们下标之间的 绝对差 。更正式地，arr[i] 和 arr[j] 之间的间隔是 |i - j| 。

返回一个长度为 n 的数组 intervals ，其中 intervals[i] 是 arr[i] 和 arr 中每个相同元素（与 arr[i] 的值相同）的 间隔之和 。

注意：|x| 是 x 的绝对值。

示例 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intervals-between-identical-elements
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 按照数字分组
• 对每组数字的 下标求前缀和，因为对 i 位置前面的可以拆成 i-i前，后面的可以拆成 i后-i
• 利用前缀和获取同符号的区间的和

class Solution {
public:
    vector getDistances(vector& arr) {
        unordered_map> pos; //  相同数字的位置
        for(int i = 0; i < arr.size(); ++i)
            pos[arr[i]].push_back(i); // 数字的各个位置
        vector ans(arr.size(), 0);
        for(auto& p : pos)
        {
            vector 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;
    }
};

340 ms 131.3 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！