题目

给你一个整数数组 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 整除的条件。

解答 & 代码

原理：两个数 a 和 b 的和可以被 k 整除（**(a + b) % k == 0**），当且仅当

case 1：**a % k == 0** 且 **b % k == 0**
case 2：**a % k + b % k == k**

因此，用哈希表（或长为 k 的数组）统计每个余数出现的次数。要使得数组中所有元素都能两两配对，则需要满足：

若余数为 0，则要求这个余数的出现次数为偶数（因为模 k 为 0 的数必须和模 k 为 0 的数匹配）
若余数 m 不为 0，则要求余数 m 的出现次数等于余数 k - m 的出现次数（因为模 k 为 m 的数必须和模 k 为 k - m 的数匹配）

另，注意：数组中元素可能为负数，因此在求余数时应写成 (arr[i] % k + k) % k 的形式，使得余数在 [0, k) 范围内

class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        int len = arr.size();
        // 哈希表，key = 余数，val = 余数出现的次数
        unordered_map<int, int> modCntMap;
        // 统计数组中元素除 k 的余数的出现次数
        for(int i = 0; i < len; ++i)
            ++modCntMap[(arr[i] % k + k) % k];    // 注意元素可能为负数，需要将余数约束到 [0, k)
        // 遍历哈希表中的所有余数
        for(auto it = modCntMap.begin(); it != modCntMap.end(); ++it)
        {
            if(it->first == 0)    // 若余数为 0，则要求出现次数为偶数次
            {
                if(it->second % 2 == 1)
                    return false;
            }
            else                // 若余数不为 0，则要求余数 m 的出现次数等于余数 k - m 的出现次数
            {
                if(it->second != modCntMap[k - it->first])
                    return false;
            }
        }
        return true;
    }
};

复杂度分析：数组长为 n，判断数组对是否可以被 k 整除

时间复杂度 O(n)：遍历数组
空间复杂度 O(k)：哈希表需要的空间，取决于数组中元素被 k 整除的余数的种数，最多为 k 种

执行结果：

执行结果：通过
执行用时：176 ms, 在所有 C++ 提交中击败了 8.99% 的用户
内存消耗：68.1 MB, 在所有 C++ 提交中击败了 25.54% 的用户

hot 100

[中等] 1497. 检查数组对是否可以被 k 整除

题目

解答 & 代码