统计数组中相等且可以被整除的数对
难度:
标签:
题目描述
代码结果
运行时间: 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)
代码细节讲解
🦆
为什么在解决这个问题时选择使用哈希表来存储数字和它们的索引列表,而不是其他数据结构如数组或链表?
▷🦆
在题解中提到的双重循环中,内层循环始终从i+1开始,这是基于什么考虑?
▷🦆
哈希表构建完成后,如果数组中有多个元素且这些元素的索引列表长度不均匀,这会对算法的性能有何影响?
▷🦆
在题解算法中,如果k为1,是否有更简单的方法来计算符合条件的数对数量?
▷