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

🟢   🔖  数组  🔗 力扣 LeetCode

题目

Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs (i, j) where 0 <= i < j < n, such thatnums[i] == nums[j] and (i * j) is divisible by k.

Example 1:

Input: nums = [3,1,2,2,2,1,3], k = 2

Output: 4

Explanation:

There are 4 pairs that meet all the requirements:

• nums[0] == nums[6], and 0 * 6 == 0, which is divisible by 2.
• nums[2] == nums[3], and 2 * 3 == 6, which is divisible by 2.
• nums[2] == nums[4], and 2 * 4 == 8, which is divisible by 2.
• nums[3] == nums[4], and 3 * 4 == 12, which is divisible by 2.

Example 2:

Input: nums = [1,2,3,4], k = 1

Output: 0

Explanation: Since no value in nums is repeated, there are no pairs (i,j) that meet all the requirements.

Constraints:

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

题目大意

给你一个下标从 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

解题思路

1. 使用一个哈希表 same 存储每个数字对应的索引数组。
2. 遍历 nums，将每个数字的索引加入 same 中。
3. 遍历 same 中每组的索引数组：
   • 如果数组长度大于 1，使用嵌套循环枚举所有可能的 (i, j)。
   • 检查 (i * j) % k == 0 是否成立，若成立则增加计数。
4. 返回累加的结果。

复杂度分析

• 时间复杂度：O(n^2)，其中 n 是数组 nums 的长度。
  • 构建 same 映射，遍历 nums 一次，时间复杂度为 O(n)。
  • 每个数组调用 getPairs，最坏情况下可能处理所有元素的两两组合，时间复杂度为 O(n^2)。
  • 整体时间复杂度为 O(n^2)，getPairs 的嵌套循环支配了复杂度。
• 空间复杂度：O(n)
  • 使用 Map 存储分组，空间复杂度为 O(n)。
  • 递归调用时的栈深度不超过数组的大小，空间复杂度为 O(n)。
  • 总空间复杂度为 O(n)。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var countPairs = function (nums, k) {
	const getPairs = (arr) => {
		let pairs = 0;
		for (let i = 0; i < arr.length; i++) {
			for (let j = i + 1; j < arr.length; j++) {
				if ((arr[i] * arr[j]) % k == 0) {
					pairs++;
				}
			}
		}
		return pairs;
	};

	let same = new Map();
	nums.forEach((num, i) => {
		if (!same.has(num)) {
			same.set(num, []);
		}
		same.get(num).push(i);
	});

	let res = 0;
	for (let arr of same.values()) {
		if (arr.length > 1) {
			res += getPairs(arr);
		}
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
2006	差的绝对值为 K 的数对数目	[✓]	数组 哈希表 计数	🟢	🀄️ 🔗
2364	统计坏数对的数目		数组 哈希表 数学 1+	🟠	🀄️ 🔗