📌 📄 内容摘要:
@SomeBottle 在 Leetcode每日一题 —— 2615. 等值距离和 中发帖
思路
也就是对于每个下标 i 对应的数字 nums[i]，要找到与其相等的所有其他数字 nums[j]，累加 abs(i-j)。
题目输入规模可能很大，时间复杂度要控制在 O(n\log n) 以下。
咱们在意的是某个数字 nums[i] 在数组内出现的所有下标，但如果直接按数字分组维护列表，扫描所耗费的时间从总体上看来是难以接受的。
既要涉及求和，而且还需要尽量是线性时间复杂度，能猜到可能能用到前缀和思想。
对于一个下标 i，我可以计算前缀中所有 i-j 之和，再计算其后缀中所有 j-i 之和，这个位置的前缀加后缀就是最终结果 arr[i] 了。
怎么生成这样的前缀和呢？从计算某个位置的前缀 prefix[i] 来思考：
比如 [1,3,1,1,1,2] 这个数组，若要计算 prefix[4]
首先 nums[4]=1，要从上一个前缀和处转移过来，我们可以用哈希...
────────── 链接信息 ──────────
🔗 论坛链接: linux.do
📎 访问地址: https://linux.do/t/topic/2035342/1
─────────────────────────────
📢 来源：LINUX DO
