1497. 检查数组对是否可以被 k 整除

🟠   🔖  数组 哈希表 计数  🔗 力扣 LeetCode

题目

Given an array of integers arr of even length n and an integer k.

We want to divide the array into exactly n / 2 pairs such that the sum of each pair is divisible by k.

Return true If you can find a way to do that orfalse otherwise.

Example 1:

Input: arr = [1,2,3,4,5,10,6,7,8,9], k = 5

Output: true

Explanation: Pairs are (1,9),(2,8),(3,7),(4,6) and (5,10).

Example 2:

Input: arr = [1,2,3,4,5,6], k = 7

Output: true

Explanation: Pairs are (1,6),(2,5) and(3,4).

Example 3:

Input: arr = [1,2,3,4,5,6], k = 10

Output: false

Explanation: You can try all possible pairs to see that there is no way to divide arr into 3 pairs each with sum divisible by 10.

Constraints:

• arr.length == n
• 1 <= n <= 10^5
• n is even.
• -10^9 <= arr[i] <= 10^9
• 1 <= k <= 10^5

题目大意

给你一个整数数组 arr 和一个整数 k ，其中数组长度是偶数，值为 n 。

现在需要把数组恰好分成 n / 2 对，以使每对数字的和都能够被 k 整除。

如果存在这样的分法，请返回 true ；否则，返回 false。

解题思路

可以采用哈希表的方式来有效检查是否能够将数组中的元素配对，使得每对元素的和可以被 k 整除：

1. 余数映射：

   • 首先，对数组中的每个元素 num 进行处理，将其对 k 取余。确保余数为正数，这样可以避免负数的影响。

2. 处理可被整除的元素：

   • 如果余数为 0，则该元素可以与另一个同样为 0 的元素配对，因此可以跳过对该元素的进一步处理。

3. 寻找互补元素：

   • 对于每个余数 num，其互补数为 k - num。这意味着，如果你有一个数 num，那么要找一个数 k - num 进行配对，使得它们的和可以被 k 整除。
   • 在哈希表中查找这个互补数 another：
     • 如果找到并且其计数大于 1，则将其计数减 1，表示找到一对可以配对的元素。
     • 如果找到但计数为 1，则删除这个互补数。
     • 如果没有找到，则将当前的余数 num 加入哈希表，记录其出现次数。

4. 最终判断：

   • 遍历完成后，检查哈希表是否为空。如果为空，表示所有元素都能够找到互补的配对，返回 true；如果不为空，表示存在无法配对的元素，返回 false。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度，因每个元素仅被处理一次。
• 空间复杂度：O(k)，哈希表的大小取决于可能的余数数量，最多为 k。

代码

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {boolean}
 */
var canArrange = function (arr, k) {
	let map = new Map();
	for (let num of arr) {
		// 处理 num，将 num 对 k 求余数，并保证余数是正数
		num = num % k;
		num = num < 0 ? k + num : num;

		// num 可以被 k 整除时
		if (num == 0) {
			continue;
		}

		// 在 map 中寻找互补元素
		// 有就将 another 减一，没有就将 num 加进 map 中
		let another = k - num;
		if (map.has(another)) {
			if (map.get(another) > 1) {
				map.set(another, map.get(another) - 1);
			} else {
				map.delete(another);
			}
		} else {
			map.set(num, (map.get(num) || 0) + 1);
		}
	}

	// 判断 map 是否为空，非空则代表无法找到互补元素
	return map.size == 0;
};

相关题目

题号	标题	题解	标签	难度
2183	统计可以被 K 整除的下标对数目		数组 数学 数论
2344	使数组可以被整除的最少删除次数		数组 数学 数论 2+
3184	构成整天的下标对数目 I		数组 哈希表 计数
3185	构成整天的下标对数目 II		数组 哈希表 计数