README.md

1497. 检查数组对是否可以被 k 整除

English Version

题目描述

给你一个整数数组 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 <= 105
• n 为偶数
• -109 <= arr[i] <= 109
• 1 <= k <= 105

解法

两个数 a 和 b 的和能被 k 整除，当且仅当这两个数对 k 取模的结果 ak 和 bk 的和就能被 k 整除。

• 如果 ak = 0，需要找到另一个满足 bk = 0 的 b 进行配对；
• 如果 ak > 0，需要找到另一个满足 bk = k - ak 的 b 进行配对。

Python3

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        mod = [0] * k
        for v in arr:
            mod[v % k] += 1
        return all(mod[i] == mod[k - i] for i in range(1, k)) and mod[0] % 2 == 0

Java

class Solution {
    public boolean canArrange(int[] arr, int k) {
        int[] mod = new int[k];
        for (int v : arr) {
            ++mod[(v % k + k) % k];
        }
        for (int i = 1; i < k; ++i) {
            if (mod[i] != mod[k - i]) {
                return false;
            }
        }
        return mod[0] % 2 == 0;
    }
}

C++

class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        vector<int> mod(k);
        for (int v : arr) ++mod[(v % k + k) % k];
        for (int i = 1; i < k; ++i)
            if (mod[i] != mod[k - i])
                return false;
        return mod[0] % 2 == 0;
    }
};

Go

func canArrange(arr []int, k int) bool {
	mod := make([]int, k)
	for _, v := range arr {
		mod[(v%k+k)%k]++
	}
	for i := 1; i < k; i++ {
		if mod[i] != mod[k-i] {
			return false
		}
	}
	return mod[0]%2 == 0
}

...