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 or false 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 <= 105
n is even.
-109 <= arr[i] <= 109
1 <= k <= 105
检查数组对是否可以被 k 整除。
给你一个整数数组 arr 和一个整数 k ，其中数组长度是偶数，值为 n 。现在需要把数组恰好分成 n / 2 对，以使每对数字的和都能够被 k 整除。
如果存在这样的分法，请返回 true ；否则，返回 false。
思路
如何判断某两个数字 a + b 的和是否可以被 k 整除？这里分两种情况
- a 和 b 各自都能被 k 整除，那么 a + b 也应该可以被 k 整除。比如 a = 9, b = 6, k = 3, a + b = 15, 15 % 3 = 0
- a 和 b 不能同时被 k 整除，但是 a % k + b % k 可以被 k 整除。比如 a = 8, b = 1, k = 9, a % k + b % k = 8 + 1 = 9 % 9 = 0
上面的推论不难得到。这道题还有第二个需要注意的点就是 input 里是有负数的。即使有负数我们也无需担心，上面提到的模运算的结合律还是成立的。这里可以手动算一下就知道。
具体做法是这里我们需要处理一下 input 数组里的每一个数字，因为他们有正有负，这里我把他们统统处理成比 k 小的正数，然后我们找与其配对的数字的时候就会比较容易了。
复杂度
时间O(n)
空间O(n)
代码
Java实现
class Solution {
public boolean canArrange(int[] arr, int k) {
int n = arr.length;
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
int temp = arr[i] % k;
if (temp < 0) {
temp += k;
}
map.put(temp, map.getOrDefault(temp, 0) + 1);
}
for (Integer key : map.keySet()) {
if (key != 0) {
int x = map.get(key);
int y = map.getOrDefault(k - key, 0);
if (x != y) {
return false;
}
} else if (map.get(0) % 2 != 0) {
return false;
}
}
return true;
}
}