2176.md

title	description	keywords
2176. 统计数组中相等且可以被整除的数对	LeetCode 2176. 统计数组中相等且可以被整除的数对题解，Count Equal and Divisible Pairs in an Array，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 2176. 统计数组中相等且可以被整除的数对 统计数组中相等且可以被整除的数对 Count Equal and Divisible Pairs in an Array 解题思路 数组

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

🟢 Easy  🔖  数组  🔗 力扣 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 that nums[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+	🟠	🀄️ 🔗