题目描述

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

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

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

样例

输入：arr = [1,2,3,4,5,10,6,7,8,9], k = 5
输出：true
解释：划分后的数字对为 (1,9),(2,8),(3,7),(4,6) 以及 (5,10)。

输入：arr = [1,2,3,4,5,6], k = 7
输出：true
解释：划分后的数字对为 (1,6),(2,5) 以及 (3,4)。

输入：arr = [1,2,3,4,5,6], k = 10
输出：false
解释：无法在将数组中的数字分为三对的同时满足每对数字和能够被 10 整除的条件。

限制

• arr.length == n
• 1 <= n <= 10^5
• n 为偶数。
• -10^9 <= arr[i] <= 10^9
• 1 <= k <= 10^5

算法

(数学) $O(n + k)$

1. 将原数组中的元素按照模 $k$ 的余数分类，统计余数为 $0$ 到 $k-1$ 的个数。
2. 如果余数为 $0$ 的个数不为偶数，则返回 false。
3. 分别从 $1$ 和 $k - 1$ 枚举 $i$ 和 $j$，如果 $r(i) \neq r(j)$ 则返回 false。
4. 最后，如果出现了 $i == j$ 的情况，需要保证 $r(i)$ 为偶数。实际上可以不判断，因为题目保证了 $n$ 是偶数，且上述过程中每一步都是成对匹配的，所以最后剩下的余数必定是偶数个。

时间复杂度

• 遍历一次原数组，然后遍历一次余数数组，时间复杂度为 $O(n + k)$。

空间复杂度

• 需要额外 $O(k)$ 的空间存储每个余数的个数。

C++ 代码

class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        vector<int> r(k, 0);
        for (int x : arr)
            r[(x % k + k) % k]++;

        if (r[0] % 2 != 0)
            return false;

        for (int i = 1, j = k - 1; i <= j; i++, j--)
            if (r[i] != r[j])
                return false;

        return true;
    }
};