LeetCode 题解工作台
检查数组对是否可以被 k 整除
给你一个整数数组 arr 和一个整数 k ，其中数组长度是偶数，值为 n 。 现在需要把数组恰好分成 n / 2 对，以使每对数字的和都能够被 k 整除。 如果存在这样的分法，请返回 true ；否则，返回 false 。 示例 1： 输入： arr = [1,2,3,4,5,10,6,7,8,9]…
3
题型
7
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
两个数 和 的和能被 整除，当且仅当这两个数分别对 取模的结果之和能被 整除。 因此，我们可以统计数组中每个数对 取模的结果，即余数，记录在数组 中。然后我们遍历数组 ，对于范围在 的每个数 ，如果 和 的值不相等，说明无法将数组中的数字分为 对，使得每对数字的和都能被 整除。如果 的值不是偶数，也说明无法将数组中的数字分为 对，使得每对数字的和都能被 整除。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 arr 和一个整数 k ，其中数组长度是偶数，值为 n 。
现在需要把数组恰好分成 n / 2 对，以使每对数字的和都能够被 k 整除。
如果存在这样的分法，请返回 true ；否则，返回 false。
示例 1：
输入：arr = [1,2,3,4,5,10,6,7,8,9], k = 5 输出：true 解释：划分后的数字对为 (1,9),(2,8),(3,7),(4,6) 以及 (5,10) 。
示例 2：
输入：arr = [1,2,3,4,5,6], k = 7 输出：true 解释：划分后的数字对为 (1,6),(2,5) 以及 (3,4) 。
示例 3：
输入：arr = [1,2,3,4,5,6], k = 10 输出：false 解释：无法在将数组中的数字分为三对的同时满足每对数字和能够被 10 整除的条件。
提示：
arr.length == n1 <= n <= 105n为偶数-109 <= arr[i] <= 1091 <= k <= 105
解题思路
方法一：统计余数
两个数 和 的和能被 整除，当且仅当这两个数分别对 取模的结果之和能被 整除。
因此，我们可以统计数组中每个数对 取模的结果，即余数，记录在数组 中。然后我们遍历数组 ，对于范围在 的每个数 ，如果 和 的值不相等，说明无法将数组中的数字分为 对，使得每对数字的和都能被 整除。如果 的值不是偶数，也说明无法将数组中的数字分为 对，使得每对数字的和都能被 整除。
时间复杂度 ，其中 为数组 的长度。空间复杂度 。
class Solution:
def canArrange(self, arr: List[int], k: int) -> bool:
cnt = Counter(x % k for x in arr)
return cnt[0] % 2 == 0 and all(cnt[i] == cnt[k - i] for i in range(1, k))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n \cdot \log n) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Candidate understands the use of hash tables for frequency counting and efficient lookups.
- question_mark
Candidate demonstrates familiarity with modular arithmetic and the concept of remainders when working with divisibility conditions.
- question_mark
Candidate can optimize a solution by using a hash table to match complementary remainders efficiently.
常见陷阱
外企场景- error
Forgetting to account for elements with a remainder of 0, which require an even count of such elements to form valid pairs.
- error
Overlooking the case where the remainder of an element is larger than half of k, leading to mismatched pairs.
- error
Assuming that elements with the same remainder can always pair together, without checking if their frequencies align properly.
进阶变体
外企场景- arrow_right_alt
What if the array has an odd length? The problem could become unsolvable since we need an even number of elements to form pairs.
- arrow_right_alt
Instead of checking divisibility by a constant k, what if the condition were a variable, such as prime numbers? The approach still works with slight modifications to the remainder check.
- arrow_right_alt
What if the problem only allowed certain ranges of numbers (e.g., only positive numbers)? The solution could be simplified since remainders would be restricted to a smaller range.