1497_检查数组对是否可以被_k_整除

类型：数组

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

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

  ❓ 把长度为 n（偶数） 的数组分成 n/2 对，使每对数字的和都能被 k 整除。如果存在这样的分法，请返回 True*，*否则返回 False 。

  💡 求余统计 + 哈希

  两个数 x 和 y 的和能被 k 整除，当且仅当 x % k 与 y % k 的和能被 k 整除。

  我们对数组中的每一个数对 k 取模并统计，以取模结果为键，出现次数为值，存入哈希表 mp。看是否满足如下配对要求：

  • 如果 x % k = 0，那么找到另一个 y % k = 0 与其配对。即模为 0 的个数要为偶数个，即 mp[0] 为偶数。
  • 如果 x % k > 0，那么需要另一个 y % k = k - x % k 预期配对。即二者的数量要相等，即，哈希表中 mp[t] 与 mp[k - t] 的值要相等。特殊情况下，当 t = k / 2（k 为偶数）时，即 t = k - t，此时 mp[t] 应该为偶数。由于此题中数组大小为偶数，在其他情况的元素都配对成功的情况下，剩下的 mp[t] 自然也是偶数。因此不用特殊考虑。

  class Solution:
      def canArrange(self, arr: List[int], k: int) -> bool:
          mod = collections.Counter(num % k for num in arr)
          for t, occ in mod.items():
              if t > 0 and (k - t not in mod or mod[k - t] != occ):
                  return False
          return mod[0] % 2 == 0

  时间复杂度：O(n)，空间复杂度：O(n)