距离之和

问题陈述

我们给定一个 0 索引的整数数组 nums。存在一个长度为 nums.length 的数组 arr，其中 arr[i] 是所有满足 nums[j] == nums[i] 且 j != i 的 j 的 |i - j| 的总和。如果不存在这样的 j，则 arr[i] 为 0。

返回数组 arr。

Java 实现

Java 暴力解法

输出

代码解释

• 提供的 Java 代码定义了一个 Solution 类，其中包含一个 distance 方法，用于计算数组中每个元素的距离。它使用一个 map 来存储每个数组元素的索引，从而在计算距离时可以高效地访问这些索引。main 函数提示用户输入数组的长度和元素，然后调用 distance 方法并输出计算出的距离。
• 对于每个数组元素，它会检查该元素是否出现一次以上，如果出现一次以上，则计算当前索引到所有其他出现位置的距离。计算出的距离存储在“result”数组中，然后打印该数组。

时间复杂度

• 给定代码的时间复杂度为 O(N^2)，其中 N 是输入数组“nums”的长度。这是因为对于数组中的每个元素，代码可能需要遍历同一元素的所有其他出现次数来计算距离。

空间复杂度

• 空间复杂度为 O(N)，这是因为需要额外的空间来在 map 中存储索引。在最坏的情况下，map 可能最多有 N 个条目，每个条目都与一个索引列表相关联。“result”数组的大小也为 N，这也会计入总的空间复杂度。

Java 前缀和方法

输出

代码解释

• 该代码计算数组中元素出现次数之间的距离。它使用 HashMap 来存储每个唯一元素的索引。对于每个元素，它根据使用索引的公式计算距离，并更新结果数组。如果元素仅出现一次，则其距离设置为 0。
• 该代码通过预先计算索引之和来有效地处理多次出现的情况。它遍历索引，更新左右和以计算距离。

时间复杂度

• 时间复杂度为 O(N)，其中 N 是输入数组的长度。该算法仅处理每个元素一次，因此时间复杂度为线性。

空间复杂度

• 空间复杂度为 O(N)，其中 N 是输入数组的长度，因为它使用 HashMap 来存储索引，并且具有与输入数组长度 N 成比例的额外空间。

使用二分查找的 Java 实现

输出

代码解释

• 上述解决方案旨在计算每个元素与其在数组中的出现次数之间的距离。它使用两个 HashMap：一个用于存储每个元素的索引，另一个用于存储每个元素的索引的前缀和。
• 它遍历数组，执行二分查找以找到当前元素在其出现次数中的索引，然后使用前缀和和索引计算距离。距离存储在结果数组中。
• 考虑了特殊情况，例如仅出现一次的元素，此时距离设置为 0。

时间复杂度

• 该解决方案遍历数组一次并执行二分查找，因此时间复杂度为 O(N log N)，其中 N 是数组的长度。

空间复杂度

• 空间复杂度为 O(N)，其中 N 是数组的长度，这是因为使用了 HashMap 来存储每个元素的索引和前缀和。