Medium

题目描述

给你一个整数数组 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 == n
  • 1 <= n <= 10^5
  • n 是偶数
  • -10^9 <= arr[i] <= 10^9
  • 1 <= k <= 10^5

解题思路

这道题的核心思路是利用余数的性质来解决配对问题。

分析配对条件： 如果两个数 a 和 b 的和能被 k 整除，那么 (a + b) % k == 0。根据模运算的性质，这等价于 (a % k + b % k) % k == 0。

余数配对规律：

  1. 余数为 0 的数只能和余数为 0 的数配对
  2. 余数为 i 的数只能和余数为 k-i 的数配对
  3. 当 k 为偶数时，余数为 k/2 的数只能和余数为 k/2 的数配对

处理负数： 由于数组中可能有负数，我们需要将负数的余数转换为正数。对于负数 x，其正余数为 ((x % k) + k) % k。

算法步骤：

  1. 统计每个余数的出现次数
  2. 检查余数为 0 的数字个数是否为偶数
  3. 对于余数 i (1 ≤ i < k)，检查余数为 i 的数字个数是否等于余数为 k-i 的数字个数
  4. 特别处理当 k 为偶数且 i == k/2 的情况，此时需要余数为 k/2 的数字个数为偶数

这种方法的时间复杂度为 O(n)，空间复杂度为 O(k)，是最优解法。

代码实现

class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        vector<int> freq(k, 0);
        
        // 统计每个余数的频次
        for (int num : arr) {
            int remainder = ((num % k) + k) % k;
            freq[remainder]++;
        }
        
        // 余数为0的数必须成对出现
        if (freq[0] % 2 != 0) {
            return false;
        }
        
        // 检查其他余数
        for (int i = 1; i <= k / 2; i++) {
            if (i == k - i) { // k为偶数，i = k/2的情况
                if (freq[i] % 2 != 0) {
                    return false;
                }
            } else {
                if (freq[i] != freq[k - i]) {
                    return false;
                }
            }
        }
        
        return true;
    }
};

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        freq = [0] * k
        
        # 统计每个余数的频次
        for num in arr:
            remainder = ((num % k) + k) % k
            freq[remainder] += 1
        
        # 余数为0的数必须成对出现
        if freq[0] % 2 != 0:
            return False
        
        # 检查其他余数
        for i in range(1, k // 2 + 1):
            if i == k - i:  # k为偶数，i = k//2的情况
                if freq[i] % 2 != 0:
                    return False
            else:
                if freq[i] != freq[k - i]:
                    return False
        
        return True

public class Solution {
    public bool CanArrange(int[] arr, int k) {
        int[] freq = new int[k];
        
        // 统计每个余数的频次
        foreach (int num in arr) {
            int remainder = ((num % k) + k) % k;
            freq[remainder]++;
        }
        
        // 余数为0的数必须成对出现
        if (freq[0] % 2 != 0) {
            return false;
        }
        
        // 检查其他余数
        for (int i = 1; i <= k / 2; i++) {
            if (i == k - i) { // k为偶数，i = k/2的情况
                if (freq[i] % 2 != 0) {
                    return false;
                }
            } else {
                if (freq[i] != freq[k - i]) {
                    return false;
                }
            }
        }
        
        return true;
    }
}

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {boolean}
 */
var canArrange = function(arr, k) {
    const remainderCount = new Array(k).fill(0);
    
    for (let num of arr) {
        let remainder = ((num % k) + k) % k;
        remainderCount[remainder]++;
    }
    
    if (remainderCount[0] % 2 !== 0) return false;
    
    for (let i = 1; i <= Math.floor(k / 2); i++) {
        if (i === k - i) {
            if (remainderCount[i] % 2 !== 0) return false;
        } else {
            if (remainderCount[i] !== remainderCount[k - i]) return false;
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n + k)遍历数组统计余数频次需要 O(n)，检查余数配对需要 O(k)
空间复杂度O(k)需要额外的数组存储每个余数的出现次数

相关题目