leetcode
leetcode 1901 ~ 1950
统计数组中相等且可以被整除的数对

统计数组中相等且可以被整除的数对

难度:

标签:

题目描述

代码结果

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


/*
 * 思路:
 * 1. 使用Java Streams的IntStream和filter方法来处理条件判断。
 * 2. 使用嵌套IntStream进行双重循环并过滤出满足条件的数对,最后计数。
 */
import java.util.stream.IntStream;

public class Solution {
    public long countPairs(int[] nums, int k) {
        return IntStream.range(0, nums.length)
            .flatMap(i -> IntStream.range(i + 1, nums.length)
                .filter(j -> nums[i] == nums[j] && (i * j) % k == 0))
            .count();
    }
}

解释

方法:

题解的核心思路是使用一个哈希表来存储数组中每个数字及其对应的索引列表。这样,对于每个数字,可以快速访问所有包含该数字的索引。接着,对于哈希表中的每一组索引列表,如果列表长度大于1(表示至少有两个相同的数字),则对这些索引进行双层循环比较,检查索引对的乘积是否能被k整除。如果可以,增加计数。

时间复杂度:

O(n^2)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在解决这个问题时选择使用哈希表来存储数字和它们的索引列表,而不是其他数据结构如数组或链表?
哈希表提供了平均时间复杂度为O(1)的快速查询和插入性能,适用于此问题中需要频繁地查找数字并追踪它们的索引。如果使用数组,虽然可以通过数字作为索引直接访问,但适用性受限于数字的范围大小。链表则不适合频繁的索引访问和搜索操作,因为链表的搜索和插入操作平均需要O(n)的时间复杂度。因此,哈希表是一个更加灵活且效率高的选择。
🦆
在题解中提到的双重循环中,内层循环始终从i+1开始,这是基于什么考虑?
内层循环从i+1开始是为了避免重复计算和自比较。因为我们只需要比较不同的索引对,并且对于任何两个索引i和j,i和j的组合已经在i小于j时考虑过了。这样可以减少计算量,确保每对索引只被计算一次,从而提高算法的效率并且避免重复计数。
🦆
哈希表构建完成后,如果数组中有多个元素且这些元素的索引列表长度不均匀,这会对算法的性能有何影响?
如果索引列表长度不均匀,那么处理较长的索引列表将消耗更多时间,尤其是在执行双重循环比较时。这可能导致算法的性能偏向于处理那些出现频率更高的元素,从而增加总体的时间复杂度。在极端情况下,如果一个数字的出现次数非常高,双重循环的时间复杂度将接近O(n^2),这可能导致性能瓶颈。
🦆
在题解算法中,如果k为1,是否有更简单的方法来计算符合条件的数对数量?
如果k为1,则任何索引乘积都满足整除条件。在这种情况下,对于任何出现两次及以上的数字,可以直接使用组合数公式C(n, 2) = n*(n-1)/2来计算每个数字的索引组合数。这样可以直接从每个索引列表的长度计算出符合条件的数对数量,避免了复杂的双重循环,从而简化算法并提高效率。

相关问题