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

https://leetcode-cn.com/problems/check-if-array-pairs-are-divisible-by-k/

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

示例 4：

输入：arr = [-10,10], k = 2
输出：true

示例 5：

输入：arr = [-1,1,-2,2,-3,3,-4,4], k = 3
输出：true

提示：

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

通过次数2,879 | 提交次数7,318

First Try

2020-07-04

这是周赛里的题目，但是第一眼看到的时候只能写出O(N^2)算法，直接就超时挂掉。看题解才知道可以用余数，真是各种小技巧。用了余数统计之后，需要考虑对立面是否相等。还有一个容易出错的是当余数为0的时候，需要确保有偶数个为0.

class Solution(object):
    def canArrange(self, arr, k):
        """
        :type arr: List[int]
        :type k: int
        :rtype: bool
        """
        # 没有经验的人怎么会有想法。。。
        # 在余数为0的时候，就不能直接按照k - 0 来选取对立面了
        # 负数好像有问题啊。。
        counter = collections.defaultdict(int)
        for a in arr:
            counter[a % k] += 1
        # print(counter)
        # 0还需要保证是偶数个数才行。。。
        if counter[0] % 2 != 0:
            return False 
        for ik, iv in counter.items():
            # 特殊操作，ik = 0时候，如果按照k - ik则是k而不是0
            # 另外还需要考虑ik = 0时候，需要有偶数位来特殊处理
            if ik == 0:
                continue
            anohterk = k - ik 
            if counter[anohterk] != iv:
                return False
        return True

执行用时：164 ms, 在所有 Python 提交中击败了51.85%的用户
内存消耗：28.4 MB, 在所有 Python 提交中击败了100.00%的用户

bug version

对0考虑不到位

class Solution(object):
    def canArrange(self, arr, k):
        """
        :type arr: List[int]
        :type k: int
        :rtype: bool
        """
        # 没有经验的人怎么会有想法。。。
        # 在余数为0的时候，就不能直接按照k - 0 来选取对立面了
        # 负数好像有问题啊。。
        counter = collections.defaultdict(int)
        for a in arr:
            counter[a % k] += 1
        print(counter)
        for ik, iv in counter.items():
            # 特殊操作，ik = 0时候，如果按照k - ik则是k而不是0
            anohterk = k - ik if ik != 0 else 0
            if counter[anohterk] != iv:
                return False
        return True

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

First Try​

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

First Try