计算具有等于 K 的差值的不同对数（Java）

给定一个整数数组 a[] 和一个正整数 k，我们的任务是计算所有差值等于 k 的不同对的数量。

示例 1

输入

int a[] = {1, 6, 7, 9, 3, 2, 8, 10}

int k = 1

输出

差值等于 k 的总对数为 6

解释

对于给定的 a[]，我们计算元素之间的差值，使其等于 k = 1。{(7 - 6 = 1); (9 - 8 = 1); (10 - 9 = 1); (3 - 2 = 1); (2 - 1 = 1); (8 - 7 = 1)}。因此，对是 {7, 6}, {9, 8}, {10, 9}, {3, 2}, {2, 1}, {8, 7}。因此，总对数为 6。

示例 2

输入

int a[] = {2, 8, 5, 3, 10, 4, 12}

int k = 2

输出

差值等于 k 的总对数为 4

解释

对于给定的 a[]，我们计算元素之间的差值，使其等于 k = 1。{(5 - 3 = 2); (10 - 8 = 2); (4 - 2 = 2); (12 - 10 = 2)}。因此，对是 {5, 3}, {10, 8}, {4, 2}, {12, 10}。因此，总对数为 4。

方法：朴素方法

一个简单的策略是逐对检查并确定它们之间的差异。下面的代码实现了这个简单的回复。执行两个循环，一个选择对的第一个元素，另一个搜索另一个元素。由于目标是仅计算不同的配对，因此如果数组包含重复项，则此技术无效。

算法

步骤 1: 初始化数组 a[] 和表示差值的 k。

步骤 2: 遍历数组 a[] 中的每个元素。

步骤 3: 对于每个元素 a[i]，遍历数组的其余项（从 a[i+1] 开始）。

步骤 4: 确定每对元素 (a[i], a[j]) 之间的差值是否等于 K 或 -K。

步骤 4.1: 在这种情况下，增加 cnt 变量的值，该变量计算具有指定差值 K 的配对数量。

步骤 5: 最后，返回这些不同配对的数量。

实施

文件名: NaiveCOuntingDiffPairs.java

输出

The total number of pairs with difference equal to k is: 4

复杂度分析

上述代码的时间复杂度为 O(N²)，其中“N”表示给定数组的长度，空间复杂度为 O(1)。

方法：使用二分查找-排序

提供的方法使用 Arrays.sort() 的排序方法，该方法将输入数组的元素按升序排列。此排序方法会就地重排数组元素；它可能基于快速排序或归并排序。对数组进行排序是必要的第一步，因为它将相似的元素组合在一起，方便删除重复项，并使查找具有所需差值的对变得更容易，从而实现高效的二分查找。通过促进对排序数组的快速操作，排序过程提高了算法的整体效率。

算法

步骤 1: 最初将计数设置为 0。

步骤 2: 将每个元素按升序排序。

步骤 3: 评估数组是否存在重复项。

步骤 4: 如下执行每个元素 a[i]。

步骤 4.1: 从 i+1 到 n-1，在子数组中对 arr[i] + k 进行二分查找。

步骤 4.2: 如果找到 arr[i] + k，则增加计数。

步骤 5: 计算计数并返回计数。

实施

文件名: SortingCountDiffPairs.java

输出

The total number of pairs with difference equal to k is: 4

复杂度分析

上述代码的时间复杂度为 O(N*logN)，其中“N”表示给定数组的长度，空间复杂度为 O(logN)。

方法：使用自平衡二叉搜索树

上述方法通过使用 AVL 树有效地控制输入元素。AVL 树在插入期间根据需要进行旋转，以保持其平衡结构并保证左右子树的高度差不超过一。搜索操作通过这种良好的平衡结构得到优化。

在 countPairsWithDiffK 函数中，AVL 树被递归扫描以查找具有给定差值 k 的对。通过在遍历期间避免计数重复项，HashSet 的使用提高了效率。由于其自平衡特性和有效的搜索能力，AVL 树是查找输入数据中差值为特定值的对的良好选择。

算法

步骤 1: 声明一个名为 Node 的类，用于表示 AVL 树中的节点。每个节点包含左子节点和右子节点的引用、键值以及高度。

步骤 2: 在插入键的同时，实现 insert 函数以平衡 AVL 树。

步骤 2.1: 修改祖先节点的高度，并在需要时旋转树以保持其平衡。

步骤 3: 使用 Rotateleft 和 Rotateright 函数分别向左和向右旋转子树，以在插入期间保持子树的平衡。

步骤 4: 声明一个名为 getBalanceFactor 的函数，该函数将计算节点的平衡因子，即其左子树和右子树之间的高度差。

步骤 5: 实现 countPairsWithDiffK 函数来计算具有特定差值 K 的对的数量。

步骤 5.1: 通过递归遍历 AVL 树并将在 HashSet 中存储遇到的键值来查找符合要求的对。

步骤 6: 在创建 CountPairsWithDiffK 的实例并将条目插入 AVL 树后，调用 countPairsWithDiffK 函数并传入给定的差值 k。

步骤 7: 显示具有给定差值 (k) 的总对数。

实施

文件名: CountPairsWithDiffK.java

输出

The total number of pairs with difference equal to k is: 4

复杂度分析

上述代码的时间复杂度为 O(N*logN)，其中“N”表示给定数组的长度，空间复杂度为 O(N)。

方法：使用哈希

哈希在 O(n) 时间复杂度下工作的一个非常基本的情况是，当值范围相对有限时。例如，在下面的实现中，值范围被假定为 0 到 99999。可以利用一种简单的哈希方法，该方法使用值作为索引。

算法

步骤 1: 主要将计数初始化为 0。

步骤 2: 用 a[] 中的每个唯一元素填充哈希映射。如果元素已存在于哈希映射中，则在插入时将其忽略。

步骤 3: 如下执行每个元素 a[i]。

步骤 3.1: 在哈希映射中搜索 a[i] + K；如果找到，则增加计数。

步骤 3.2: 在哈希映射中搜索 a[i] - K；如果找到，则增加计数。

步骤 3.3: 从哈希表中删除 arr[i]。

步骤 4: 返回计数

实施

文件名: HashingCountDistinctPairs.java

输出

The total number of pairs with difference equal to k is: 4

复杂度分析

上述代码的时间复杂度为 O(N)，其中“N”表示给定数组的长度，空间复杂度为 O(N)。