目标
给你一个下标从 0 开始的整数数组 nums 。现有一个长度等于 nums.length 的数组 arr 。对于满足 nums[j] == nums[i] 且 j != i 的所有 j ，arr[i] 等于所有 |i - j| 之和。如果不存在这样的 j ，则令 arr[i] 等于 0 。
返回数组 arr 。
示例 1：
输入：nums = [1,3,1,1,2]
输出：[5,0,3,4,0]
解释：
i = 0 ，nums[0] == nums[2] 且 nums[0] == nums[3] 。因此，arr[0] = |0 - 2| + |0 - 3| = 5 。
i = 1 ，arr[1] = 0 因为不存在值等于 3 的其他下标。
i = 2 ，nums[2] == nums[0] 且 nums[2] == nums[3] 。因此，arr[2] = |2 - 0| + |2 - 3| = 3 。
i = 3 ，nums[3] == nums[0] 且 nums[3] == nums[2] 。因此，arr[3] = |3 - 0| + |3 - 2| = 4 。
i = 4 ，arr[4] = 0 因为不存在值等于 2 的其他下标。示例 2：
输入：nums = [0,5,3]
输出：[0,0,0]
解释：因为 nums 中的元素互不相同，对于所有 i ，都有 arr[i] = 0 。说明：
- 1 <= nums.length <= 10^5
- 0 <= nums[i] <= 10^9
思路
有一个整数数组 nums，返回一个等长数组 arr，arr[i] 等于所有与 nums[i] 相等的 nums[j] 到下标 i 的距离之和，即 Σ|i - j|，如果不存在这样的 j 则距离为 0。
使用哈希表将元素分组，假定某一组内的元素为 a0 < a1 < …… < a_(m - 1)，令 S0 = Σ_(j ∈ [0, m - 1])(aj - a0)，考虑 S1 - S0，原来所有元素到 a0 的距离变成了所有元素到 a1 的距离：组内下标小于 1 的距离都增加了 a1 - a0，组内下标大于等于 1 的距离都减少了 a1 - a0。
更一般的情况 Si - S_(i - 1)，组内下标小于 i 的元素到 a_(i - 1) 的距离都增加了 a_i - a_(i - 1)，组内下标大于等于 i 的元素到 a_(i - 1) 的距离都减小了 a_i - a_(i - 1)。组内下标小于 i 的元素有 i 个，组内下标大于等于 i 的元素有 m - i 个，Si - S_(i - 1) = i * (ai - a_(i - 1)) - (m - i) * (ai - a_(i - 1)) = (2 * i - m) * (ai - a_(i - 1))。
代码
/**
* @date 2026-04-23 9:46
*/
public class Distance2615 {
public long[] distance(int[] nums) {
int n = nums.length;
long[] res = new long[n];
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < n; i++) {
map.putIfAbsent(nums[i], new ArrayList<>());
map.get(nums[i]).add(i);
}
for (List<Integer> list : map.values()) {
if (list.size() > 1) {
long s = 0L;
int start = list.get(0);
for (int i = 1; i < list.size(); i++) {
s += list.get(i) - start;
}
res[start] = s;
for (int i = 1; i < list.size(); i++) {
res[list.get(i)] = res[list.get(i - 1)] + (2 * i - list.size()) * (list.get(i) - list.get(i - 1));
}
}
}
return res;
}
}
性能
