leetcode
leetcode 1751 ~ 1800
差的绝对值为 K 的数对数目

差的绝对值为 K 的数对数目

难度:

标签:

题目描述

代码结果

运行时间: 30 ms, 内存: 16.1 MB


/**
 * Approach: We use Java Streams to iterate through the array and count the pairs 
 * satisfying the condition using IntStream and filter.
 *
 * Time Complexity: O(n^2) where n is the number of elements in nums.
 * Space Complexity: O(1) as we are not using any additional space.
 */
import java.util.stream.IntStream;

public class Solution {
    public int countKDifference(int[] nums, int k) {
        return (int) IntStream.range(0, nums.length)
            .flatMap(i -> IntStream.range(i + 1, nums.length)
                .filter(j -> Math.abs(nums[i] - nums[j]) == k))
            .count();
    }
}

解释

方法:

这个题解采用了哈希表的方法。首先,遍历数组nums,用一个字典dic来记录每个元素出现的次数。然后,再次遍历字典中的每个元素,检查其与k之差是否也在字典中。如果是,那么这两个数就可以形成满足条件的数对。由于我们是在字典中查找,因此可以保证数对中的第一个数小于第二个数,从而避免了重复计算。最后,将所有满足条件的数对数量累加起来,就得到了最终的答案。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在解题思路中,为什么选择使用哈希表来记录元素出现的次数,而不是其他数据结构如数组或链表?
哈希表(或字典)在这种场景下使用主要是因为它提供了非常快速的查找、插入和更新操作的平均时间复杂度,通常是O(1)。对于本题目,需要频繁地检查元素是否存在于集合中并更新元素的计数,哈希表可以非常高效地支持这些操作。而使用数组虽然也可以实现,但当元素范围很大或非连续时,会造成空间的浪费或无法实现。链表则因为查找和更新操作需要O(n)的时间复杂度而不适合。
🦆
给出的解法中,为何确保通过字典来查找元素可以避免重复计算,具体是怎样实现的?
在算法中,通过确保只计算`item - k`(其中`item`是字典的键)的情况,而不是同时计算`item + k`和`item - k`,可以避免重复。具体来说,当我们考虑每个元素`item`时,只检查`item - k`是否存在于字典中,这样就只统计每个满足条件的数对一次,因为对于每个数对(a, b),我们只在处理`b`时计算`b - a = k`,而不会在处理`a`时重复计算`a - b = k`。
🦆
在代码实现中,遍历字典时检查`item - k`是否存在于字典中,这种方法是否考虑了`item + k`的情况,两者之间有何不同?
代码中确实只考虑了`item - k`的情况,并没有直接考虑`item + k`。这是因为选取任一方向(`item - k`或`item + k`)就足以覆盖所有可能的数对,而且可以避免重复计算。如果同时考虑`item + k`,则需要额外的逻辑来确保不重复计算同一对数。因此,选择任一方向检查就可以有效地实现需求,并简化代码逻辑。
🦆
当`k`的值为0时,这种算法处理的逻辑是什么?是否需要特别处理,他们的计数方法有何不同?
当`k`为0时,题目要求找出相同数值的数对。在这种情况下,算法在统计时需要略作调整,即对于每个元素`item`,计算其在字典中的出现次数`dic[item]`,然后使用组合数公式计算可以形成的数对数目:`dic[item] * (dic[item] - 1) / 2`。这是因为每对相同的元素都可以形成一个数对,而每个元素可以与之前的相同元素组成数对。

相关问题