等值距离和

You are given a 0-indexed integer array nums. There exists an array arr of length nums.length, where arr[i] is the sum of |i - j| over all j such that nums[j] == nums[i] and j != i. If there is no such j, set arr[i] to be 0.

Return the array arr.

 

Example 1:

Input: nums = [1,3,1,1,2]
Output: [5,0,3,4,0]
Explanation: 
When i = 0, nums[0] == nums[2] and nums[0] == nums[3]. Therefore, arr[0] = |0 - 2| + |0 - 3| = 5. 
When i = 1, arr[1] = 0 because there is no other index with value 3.
When i = 2, nums[2] == nums[0] and nums[2] == nums[3]. Therefore, arr[2] = |2 - 0| + |2 - 3| = 3. 
When i = 3, nums[3] == nums[0] and nums[3] == nums[2]. Therefore, arr[3] = |3 - 0| + |3 - 2| = 4. 
When i = 4, arr[4] = 0 because there is no other index with value 2. 

Example 2:

Input: nums = [0,5,3]
Output: [0,0,0]
Explanation: Since each element in nums is distinct, arr[i] = 0 for all i.

 

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109

/*
 * 思路：
 * 1. 使用 Java Stream API 对数组进行处理。
 * 2. 遍历 nums 数组，使用 filter 和 map 操作找到所有相同元素的索引，并计算距离之和。
 * 3. 如果没有其他相同的元素，将对应位置的值设为 0。
 */

import java.util.stream.IntStream;

public class Solution {
    public int[] distanceArray(int[] nums) {
        return IntStream.range(0, nums.length)
            .map(i -> IntStream.range(0, nums.length)
                .filter(j -> i != j && nums[i] == nums[j])
                .map(j -> Math.abs(i - j))
                .sum())
            .toArray();
    }
}

该题解采用的是使用哈希表来记录每个数字及其出现的所有索引位置。接下来，对于哈希表中的每个条目，如果一个数字出现不止一次，则计算与该数字相等的所有数组元素之间的距离和。为了高效地计算距离和，使用累积和技巧。对于每个索引位置i，使用公式：\(ans[num] = num \times i - pre[i] + pre[-1] - num \times (m - i) - pre[i]\)，其中\(pre\)是索引位置的累积和数组，\(m\)是当前数字的出现次数。这种方法避免了对每个索引对的显式距离计算，从而提高了效率。

O(n)

O(n)