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

2022-03-18 HGNULB 约 8 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

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

题意分析

给一个长度为偶数的数组，问能不能把所有元素两两配对、一个不剩，使得每一对的和都能被 $k$ 整除。只要求判断可行性，不需要给出具体的配对方案。

「一个不剩」是最强的约束：这不是从数组里挑若干对出来，而是完美匹配，所以任何一个元素落单都直接判否。

元素可以是负数，取值范围到 $\pm 10^9$。这一点决定了不能直接用语言内置的 %，因为 C 系语言的取余结果符号跟随被除数，$-1 \bmod 5$ 会得到 $-4$ 而不是数学上的 4，用它当数组下标会越界。

数组长度和 $k$ 都可以到 $10^5$，允许线性扫描并开一个长度为 $k$ 的辅助数组。

解法：余数计数

核心思路

暴力做法是回溯：挑一个元素，在剩下的里找一个能配对的，递归下去。搜索树的规模是 $(n-1)!!$ 级别，$n$ 才十几就跑不动了。

观察在于「一对的和能否被 $k$ 整除」完全不看两个数本身，只看它们对 $k$ 的余数。若 $a \equiv r$、$b \equiv s \pmod k$，则 $a + b \equiv r + s$，能被整除当且仅当 $r + s \equiv 0 \pmod k$。于是原数组可以被压成一张长度为 $k$ 的余数频次表，元素的身份彻底消失，剩下的只是「哪一类和哪一类配」。

每个余数 $r$ 的唯一合法搭档是 $k - r$（$r = 0$ 时搭档是自己）。这些配对关系把 $0$ 到 $k-1$ 划成了互不相交的组，因此可行性可以逐组独立判断，整体可行等价于每一组都能内部消完。

由此得到判定条件，也就是这题的不变量：记 $cnt[r]$ 为余数等于 $r$ 的元素个数，则完美配对存在当且仅当 —— $cnt[0]$ 是偶数（余数 0 只能内部两两配对）；对每个 $0 < r < k/2$ 有 $cnt[r] = cnt[k-r]$（这两类必须一一对应，多一个少一个都会落单）；当 $k$ 是偶数时 $cnt[k/2]$ 也是偶数（因为 $k/2 + k/2 = k$，这一类同样只能内部配对）。

这三条既必要又充分：必要性上面已经逐条说明，充分性则是因为条件成立时可以直接构造——把 $cnt[0]$ 和 $cnt[k/2]$ 内部两两牵手，把 $r$ 类和 $k-r$ 类按顺序一一对上，正好用完所有元素。

解题步骤

开一个长度为 $k$ 的计数数组 count。下标就是余数，这里用数组而非哈希表，是因为余数天然落在 $[0, k)$ 这个稠密区间里，数组更快也更省。

遍历数组，对每个元素算 r = val % k，若 r < 0 就补上一个 k。这一步专门修正负数取余的符号问题，不补的话既会拿到负下标，也会把本该互补的两类分到不同桶里。

先查 count[0] % 2 != 0，是就返回 false。余数为 0 的数只能彼此配对，个数为奇数时必然有一个落单。

循环 r 从 1 开始、条件为 r * 2 < k，逐个比较 count[r] 与 count[k - r]，不等就返回 false。用 r * 2 < k 而不是 r < k / 2，可以在 $k$ 为奇数时也精确停在中点前，同时天然避开把 $k/2$ 这一类重复检查两遍。

若 $k$ 为偶数，单独检查 count[k / 2] 是否为偶数。这一类的搭档是它自己，规则与余数 0 完全一致，而上一步的循环恰好没覆盖到它。

所有检查通过就返回 true。此时每一组余数都能自洽消完，配对方案一定存在。

以 arr = [1,2,3,4,5,10,6,7,8,9], k = 5 走一遍：逐个取模，$1, 2, 3, 4$ 分别落进桶 1、2、3、4；$5 \bmod 5 = 0$、$10 \bmod 5 = 0$ 落进桶 0；$6, 7, 8, 9$ 又分别落进桶 1、2、3、4。最终 count = [2, 2, 2, 2, 2]。检查 count[0] = 2 是偶数，通过。进入循环：$r = 1$ 时 $1 \times 2 = 2 < 5$，比较 count[1] = 2 与 count[4] = 2，相等；$r = 2$ 时 $4 < 5$，比较 count[2] = 2 与 count[3] = 2，相等；$r = 3$ 时 $6 < 5$ 不成立，循环结束。$k = 5$ 是奇数，跳过中点检查，返回 true。实际配对是 $(5,10)$、$(1,9)$、$(6,4)$、$(2,8)$、$(7,3)$，每一对的和都是 5 的倍数。

代码实现

class Solution {
    // 余数 r 必须和余数 k - r 配对，因此两类余数的出现次数必须相等。
    public boolean canArrange(int[] arr, int k) {
        int[] count = new int[k];
        for (int val : arr) {
            int r = val % 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 {
    // 余数 r 必须和余数 k - r 配对，因此两类余数的出现次数必须相等。
    count := make([]int, k)
    for _, val := range arr {
        r := val % 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)$，一趟取模统计是 $O(n)$，随后对余数区间的对称检查是 $O(k)$，两者互不嵌套。

空间复杂度：$O(k)$，只有一个长度为 $k$ 的计数数组，与数组长度无关。

关键点总结

判断「和能否被 $k$ 整除」时，元素本身的值是无关信息，只有它对 $k$ 的同余类有意义。把数组压成余数频次表是这类题的第一动作。

完美匹配问题可以按「谁能和谁配」把候选集划成互不相交的组，组间独立、组内自洽，判定条件就能逐组给出而不必真的去搜索方案。

自配对的余数（$0$ 和 $k/2$）与互配对的余数遵循不同规则，前者要求个数为偶，后者要求两边相等。这两类必须分开处理。

负数取余在 C、Java、Go 里符号跟随被除数，凡是拿余数当下标或当哈希键，都要先做 r < 0 ? r + k : r 的规范化。

面试视角：这题代码只有十几行，考的是能不能把「配对可行性」严格归约成三条计数条件，并说清充分性。只报出「统计余数」而讲不出为什么这三条就够，通常会被继续追问；$k$ 为偶数时的中点情形则是最常见的现场踩坑点。

易错点总结

错误写法：直接用 val % k 当下标，不做负数修正：arr = [-1,1], k = 2 → $-1 \bmod 2$ 在 Java 和 Go 里都是 $-1$，count[-1] 立刻抛数组越界或 panic。

错误写法：改用哈希表存原始余数、不做归一化：arr = [-1,4], k = 5 → $-1$ 记在键 $-1$ 上、$4$ 记在键 $4$ 上，两者本该互补却被当成两类，返回 false，而正确答案是 true。

错误写法：只做互补相等检查，把 count[0] 和 count[k / 2] 的两条奇偶校验一并省掉：arr = [4,2], k = 4 → 余数是 0 和 2，count[1] = count[3] = 0 相等，检查全部通过返回 true，而 $4 + 2 = 6$ 根本不能被 4 整除，正确答案是 false。

错误写法：只保留 count[0] 或只保留 count[k / 2] 其中一条，以为另一条冗余 → 在数组长度为偶数的前提下这两个计数的奇偶性总是同步，留一条确实能兜住上面那个用例，但一旦题面放宽成长度可为奇数，或把这套判定挪到别的场景，剩下的那条就拦不住了，两条都写出来才是安全的。

错误写法：循环写成 for (r = 1; r <= k / 2; r++) 并在里面比较 count[r] 与 count[k - r] → $k$ 为偶数时 $r = k/2$ 会拿 count[k/2] 和自己比，恒等成立，等于放过了本该做的奇偶检查。

错误写法：循环起点写成 r = 0 → 比较 count[0] 与 count[k]，后者直接越界；即便侥幸不越界，余数 0 的规则也不是「与 $k - 0$ 相等」。

错误写法：把条件放宽成 count[r] + count[k - r] 为偶数 → arr = [1,1,1,3], k = 4 的余数是 $1,1,1,3$，两类之和为 4 是偶数，但 $1$ 类有三个、$3$ 类只有一个，实际无法完美配对，会错误返回 true。

错误写法：忽略数组长度必为偶数这一前提、试图在长度为奇数时也返回 true → 题目虽保证长度为偶，但若把这套判定照搬到不保证的变体上，需要额外补一条整体奇偶校验。

错误写法：用排序加双指针替代计数 → 元素本身有序不代表余数有序，负数和大数混排后指针配对逻辑会错乱，而且复杂度反而升到 $O(n \log n)$。

相似题目

题目	难度	考察点
1010. 总持续时间可被 60 整除的歌曲	中等	同样按余数互补配对，但要统计对数而非判可行
974. 和可被 K 整除的子数组	中等	对象换成前缀和的余数，配对条件从互补变成相等
523. 连续的子数组和	中等	同余前缀和还需附带长度至少为 2 的限制
560. 和为 K 的子数组	中等	前缀和差值的精确匹配，不涉及取模
1. 两数之和	简单	只需找出一对，边遍历边查表即可
面试题 16.24. 数对和	中等	要求返回全部配对方案，计数表还得反向还原元素