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

约 5 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 微软 快手
标签
数组 哈希表 计数

题目描述

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

image-20260928230309448

image-20260928230309449

题意分析

数组长度为偶数，要把全部元素分成若干对，每个元素恰好使用一次，并使每一对的和都能被正整数 k 整除。

只返回是否能够完成配对，不需要输出具体数对。数组可能含负数，不能只按正数情况计算余数；整个数组总和能被 k 整除也不足以保证逐对可行。

解法：余数计数

核心思路

[!blue]

两个数的和能否被 k 整除，只由它们的余数决定。将余数统一为 0..k-1 后，余数 r 只能与 (k-r) % k 配对，同一余数类别中的具体原值不再影响判断。

对不同的互补类别 r 与 k-r，每一对都各消耗一项，想用完两边，频次必须相等。这也足够：两边任意一一对应就能全部配完。

有两种自互补类别需要单独处理。余数零只能与零配对，数量必须为偶数；若 k 为偶数，余数 k/2 加自身恰好等于 k，同样需要偶数项。把这些类别内每两个配成一对，其余类别成对匹配，就覆盖全部元素，证明条件既必要又充分。

Java 和 Go 对负数取余可能得到负值。先取余，如果小于零就加一次 k，即可规范到合法数组下标，不改变模意义。

解题步骤

  1. 创建长度为 k 的计数数组，统计每个元素的规范余数。
  2. 检查余数零的频次是否为偶数。
  3. 对 1 <= r < k-r，检查 count[r] == count[k-r]，每对类别只检查一次。
  4. 若 k 为偶数，再检查中间余数的频次是否为偶数。
  5. 任一条件不满足则失败，全部满足返回成功。

代码实现

class Solution {
    // 不同的互补余数频次相等；零和中间余数在自身类别内两两配对。
    public boolean canArrange(int[] arr, int k) {
        int[] count = new int[k];

        for (int val : arr) {
            int r = val % k;

            // 把负余数规范到零至 k 减一，保证计数下标合法。
            if (r < 0) {
                r += k;
            }

            count[r]++;
        }

        // 余数零只能与同类配对，数量必须为偶数。
        if (count[0] % 2 != 0) {
            return false;
        }

        for (int r = 1; r * 2 < k; r++) {
            if (count[r] != count[k - r]) {
                return false;
            }
        }

        // 偶数模数的中间余数同样只能与自身配对。
        if (k % 2 == 0 && count[k / 2] % 2 != 0) {
            return false;
        }

        return true;
    }
}

func canArrange(arr []int, k int) bool {
    // 不同的互补余数频次相等；零和中间余数在自身类别内两两配对。
    count := make([]int, k)
    for _, val := range arr {
        r := val % k
        // 把负余数规范到零至 k 减一，保证计数下标合法。
        if r < 0 {
            r += k
        }
        count[r]++
    }

    // 余数零只能与同类配对，数量必须为偶数。
    if count[0]%2 != 0 {
        return false
    }

    for r := 1; r*2 < k; r++ {
        if count[r] != count[k-r] {
            return false
        }
    }

    // 偶数模数的中间余数同样只能与自身配对。
    if k%2 == 0 && count[k/2]%2 != 0 {
        return false
    }

    return true
}

复杂度分析

  • 时间复杂度：$O(n+k)$，统计遍历 $n$ 个数，初始化和检查余数类别为 $O(k)$。
  • 空间复杂度：$O(k)$，用于余数频次数组。

关键点总结

[!green]

  • 配对要求按模压缩成互补余数关系，无需尝试所有数对。
  • 不同类别要求数量相等，自互补类别要求数量为偶数。
  • 这些计数条件可以直接构造出完整配对，因此不仅是必要条件。

易错点总结

[!yellow]

  • 直接把负余数作下标会越界，需要先规范化。
  • 只看某个互补余数是否存在，无法保证有足够数量逐项配完。
  • 只检查总和整除，不能排除某一类别缺少互补元素。
  • 中间余数与自身比较频次永远相等，必须检查偶数性，不能混在普通类别条件里。
  • k == 1 时只有余数零，其余循环自然为空，不应访问不存在的类别。

相似题目

题目 难度 关联与区别
1010. 总持续时间可被 60 整除的歌曲 中等 同样按余数配对，本题要求全部元素都能配完，所以互补余数频次必须兼容。
1679. K 和数对的最大数目 中等 原题求最大可配对数量，本题是全部配对的可行性，并需单独检查自互补余数的偶数频次。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/56224445
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！