计算可被 k 整除的数组对

问题陈述

给定一个长度为 n 的 0 索引整数数组 nums 和一个整数 k，返回满足以下条件的数对 (i, j) 的数量：

• 0 <= i < j <= n - 1 且
• nums[i] * nums[j] 可以被 k 整除。

Java 方法一：频率计数

输出

代码解释

• 上述 Java 代码旨在计算数组中两个元素的乘积能被给定值 k 整除的数对数量。它使用一个 Map 来存储 GCD 值的计数，并遍历数组来填充此 Map。
• 然后，它遍历 Map 以查找 GCD 等于 k 的数对，并相应地更新结果。代码使用 BigInteger 来计算 GCD，以处理大数。

时间复杂度

• 所提供代码的时间复杂度约为 O(n^2)，其中 n 是输入数组 nums 的长度。这是因为嵌套循环会遍历 cnt Map。
• 外层循环遍历唯一的 GCD 值，内层循环比较并计算 GCD 等于 k 的数对。

空间复杂度

• 空间复杂度为 O(n)，因为代码使用 HashMap 来存储 GCD 频率，在最坏的情况下，它可能包含 n 个唯一的 GCD 值。

缺点

• 代码在时间和空间效率方面都存在不足。它使用了嵌套循环，导致时间复杂度为 O(n^2)，这对于大型输入可能不实用。此外，它还使用 HashMap 来存储 GCD 频率，导致 O(n) 的空间复杂度。
• 内层循环中低效的成对比较导致算法优化不足。

Java 方法二：计数和组合数学的结合

输出

代码解释

• 该代码旨在计算数组中两个元素的 GCD 等于给定值 k 的数对数量。它使用一个数组 cntgcd 来存储 GCD 值的频率。代码遍历数组，为每个元素计算 GCD，然后根据 GCD 值计算数对的数量。
• 该方法有效地处理了各种情况，例如 GCD 小于 k 或 k 可被 GCD 整除的情况。

时间复杂度

• 所提供代码的时间复杂度为 O(n)，其中 n 是输入数组 nums 的长度。代码遍历数组为每个元素计算 GCD，然后根据 GCD 值计数数对。

空间复杂度

• 空间复杂度为 O(k)，其中 k 是给定的输入值。它使用一个数组 cntgcd 来存储 GCD 值的频率，这会影响总体空间复杂度。