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

难度: Easy

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k ，请你返回满足 0 <= i < j < n ，nums[i] == nums[j] 且 (i * j) 能被 k 整除的数对 (i, j) 的数目。

示例 1：

输入：nums = [3,1,2,2,2,1,3], k = 2
输出：4
解释：
总共有 4 对数符合所有要求：
- nums[0] == nums[6] 且 0 * 6 == 0 ，能被 2 整除。
- nums[2] == nums[3] 且 2 * 3 == 6 ，能被 2 整除。
- nums[2] == nums[4] 且 2 * 4 == 8 ，能被 2 整除。
- nums[3] == nums[4] 且 3 * 4 == 12 ，能被 2 整除。

示例 2：

输入：nums = [1,2,3,4], k = 1
输出：0
解释：由于数组中没有重复数值，所以没有数对 (i,j) 符合所有要求。

提示：

1 <= nums.length <= 100
1 <= nums[i], k <= 100

Submission

运行时间: 38 ms

内存: 16.1 MB

class Solution:
    def countPairs(self, nums: List[int], k: int) -> int:
        ds = {}
        for i,v in enumerate(nums):
            ds[v] = ds.get(v,[])
            ds[v].append(i)
        
        ans = 0
        for v in ds.values():
            l = len(v)
            if l > 1:
                for i in range(l-1):
                    for j in range(i+1,l):
                        if v[i] * v[j] % k == 0:
                            ans += 1
        return ans

Explain

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

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def countPairs(self, nums: List[int], k: int) -> int:
        ds = {}
        # 构建哈希表，键是数字，值是这个数字出现的所有索引
        for i, v in enumerate(nums):
            ds[v] = ds.get(v, [])
            ds[v].append(i)
        
        ans = 0
        # 遍历每个数字的索引列表
        for v in ds.values():
            l = len(v)
            # 如果列表中至少有两个索引，进行双重循环
            if l > 1:
                for i in range(l-1):
                    for j in range(i+1, l):
                        # 检查索引乘积是否能被k整除
                        if v[i] * v[j] % k == 0:
                            ans += 1
        return ans

Explore

哈希表提供了平均时间复杂度为O(1)的快速查询和插入性能，适用于此问题中需要频繁地查找数字并追踪它们的索引。如果使用数组，虽然可以通过数字作为索引直接访问，但适用性受限于数字的范围大小。链表则不适合频繁的索引访问和搜索操作，因为链表的搜索和插入操作平均需要O(n)的时间复杂度。因此，哈希表是一个更加灵活且效率高的选择。

内层循环从i+1开始是为了避免重复计算和自比较。因为我们只需要比较不同的索引对，并且对于任何两个索引i和j，i和j的组合已经在i小于j时考虑过了。这样可以减少计算量，确保每对索引只被计算一次，从而提高算法的效率并且避免重复计数。

如果索引列表长度不均匀，那么处理较长的索引列表将消耗更多时间，尤其是在执行双重循环比较时。这可能导致算法的性能偏向于处理那些出现频率更高的元素，从而增加总体的时间复杂度。在极端情况下，如果一个数字的出现次数非常高，双重循环的时间复杂度将接近O(n^2)，这可能导致性能瓶颈。

如果k为1，则任何索引乘积都满足整除条件。在这种情况下，对于任何出现两次及以上的数字，可以直接使用组合数公式C(n, 2) = n*(n-1)/2来计算每个数字的索引组合数。这样可以直接从每个索引列表的长度计算出符合条件的数对数量，避免了复杂的双重循环，从而简化算法并提高效率。