LeetCode 982. 按位与为零的三元组

2023-07-27 HGNULB 约 10 分钟

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

分类

题目描述

✅ 982. 按位与为零的三元组

题意分析

给一个整数数组 nums，统计满足 nums[i] & nums[j] & nums[k] == 0 的三元组 (i, j, k) 的个数。

第一件要读准的事是：这里数的是下标三元组，i、j、k 各自独立地取遍 0..n-1，允许重复取到同一个下标，也区分顺序。所以 [0,0,0] 这样的输入答案是 $3^3 = 27$ 而不是 1。这一点决定了不能套用三数之和那种「i < j < k」的去重模板——恰恰相反，正因为三个位置完全独立，才可以把它们拆开分别统计。

第二件事是约束给出的强信号。nums.length 最大 1000，所以 $O(n^3) = 10^9$ 超时，$O(n^2) = 10^6$ 完全可以接受。而 nums[i] < 2^16 意味着任何按位与的结果也都在 $[0, 2^{16})$ 内，取值空间被封死在 65536 以内——一个远小于 $n^2 = 10^6$ 的常数。题目把值域写得这么具体，就是在提示「把两两组合的结果按值归并」。

第三，按位与的性质：a & b & c == 0 等价于「对每一个二进制位，a、b、c 中至少有一个在该位是 0」。更有用的等价形式是把它拆成两步——先算 mask = a & b，再要求 mask & c == 0，也就是 c 的二进制 1 位必须完全落在 mask 的 0 位里。

边界方面：数组中出现 0 时，任何含它的组合都满足条件；全部元素都是 2^16 - 1 时答案为 0。数组长度至少为 1，不存在空输入。答案上界是 $1000^3 = 10^9$，仍在 32 位有符号整数范围内（约 21 亿），不必上 long，但这一点值得在面试中主动核对。

解法：统计两两按位与 + 枚举第三个数

核心思路

暴力是三重循环枚举 i, j, k，共 $10^9$ 次按位与判断，必然超时。

瓶颈在于第三层循环被反复重跑：对固定的 (i, j)，内层要把全部 n 个 k 走一遍；而很多不同的 (i, j) 其实产生了完全相同的 a & b。既然判断 mask & c == 0 只依赖 mask 的值而不依赖 i、j 具体是谁，那么值相同的 (i, j) 对就可以合并成一条「这个 mask 出现了多少次」的记录。

于是解法拆成两个阶段：

阶段一：双重循环枚举所有有序对 (i, j)，统计 cnt[a & b] —— 键是按位与的结果，值是产生该结果的有序对数量。这一步是 $O(n^2)$，共 $10^6$ 次，且由于值域封顶，键的种类不超过 65536。

阶段二：枚举第三个数 c，对表中每个 (mask, times)，若 mask & c == 0 就把 times 累加进答案。这一步是 $O(n \cdot U)$，U 是表中不同键的数量。

正确性来自计数的一一对应：每个满足条件的下标三元组 (i, j, k) 在阶段一里贡献了 cnt[nums[i] & nums[j]] 的 1 个计数，在阶段二里被 c = nums[k] 恰好统计一次；反过来阶段二累加的每一份计数也都对应唯一的一个合法三元组。因为 (i, j) 是有序对（i 和 j 各自独立遍历全数组），所以顺序与重复下标都被自然地计入，正好匹配题目对三元组的定义。

维持的不变量是：阶段一结束时，cnt 中所有值之和恰好等于 $n^2$（每个有序对贡献 1）；阶段二每次累加的 times 都是「与当前 c 相容的有序对数量」。两个不变量合起来保证答案既不重复也不遗漏。

这里用哈希表而不是长度 65536 的数组，是因为实际出现的 mask 种类往往远少于 65536（按位与只会让 1 位变少，结果高度集中），遍历时能跳过大量不可达的键。若追求更稳定的常数，换成定长数组同样可行，只是要遍历全部 65536 个下标。

解题步骤

阶段一：统计两两与的结果。双重循环让 a 与 b 各自遍历整个 nums，把 cnt[a & b] 加一。为什么两层都要跑满 n 而不是写成 j > i：题目的三元组区分顺序且允许下标重合，跑满才能让计数与题意一一对应；若只枚举 i < j 再乘 2，还得单独补上 i == j 的情况，反而更容易错。

为什么键取 a & b 而不是保留 (a, b)：判断第三个数是否相容只用得到 a & b，保留更多信息不会提高精度，只会让键的种类爆炸，失去归并的意义。

阶段二：枚举第三个数。外层遍历 c，内层遍历 cnt 的每个键值对，条件 (mask & c) == 0 成立时 answer += times。为什么加的是 times 而不是 1：这个 mask 背后站着 times 个不同的有序对 (i, j)，它们与当前的 k 各自组成一个合法三元组。

为什么条件是 mask & c == 0 而不是 mask == c 或包含关系的其他写法：a & b & c == 0 按结合律等于 (a & b) & c == 0，直接就是这个形式；它的含义是 c 的每个 1 位在 mask 上都必须是 0。

注意运算符优先级：Java 中 & 的优先级低于 ==，必须写成 (mask & c) == 0，漏掉括号会被解析成 mask & (c == 0) 而编译报错（Go 里 & 优先级高于 ==，可以不加括号，但加上更清晰）。

返回答案。

以 nums = [2, 1, 3] 走一遍（预期答案 12）。二进制分别是 10、01、11。
阶段一枚举 9 个有序对：2&2=2、2&1=0、2&3=2、1&2=0、1&1=1、1&3=1、3&2=2、3&1=1、3&3=3。归并得 cnt = {2:3, 0:2, 1:3, 3:1}，四个值之和为 9 = $3^2$，与不变量吻合。
阶段二逐个枚举 c：
c = 2（10）：mask = 2 时 2 & 2 = 2 != 0，不计；mask = 0 时 0 & 2 = 0，累加 2；mask = 1 时 1 & 2 = 0，累加 3；mask = 3 时 3 & 2 = 2 != 0，不计。小计 5。
c = 1（01）：mask = 2 时 2 & 1 = 0，累加 3；mask = 0 累加 2；mask = 1 时 1 & 1 = 1，不计；mask = 3 时不计。小计 5。
c = 3（11）：只有 mask = 0 相容，累加 2。小计 2。
合计 5 + 5 + 2 = 12，与预期一致。

再看 nums = [0, 0, 0]：阶段一得 cnt = {0: 9}；阶段二每个 c = 0 都与 mask 0 相容，累加 9，三次共 27，正好是 $3^3$——所有三元组都合法，验证了「区分顺序、允许重复」的计数口径。

代码实现

class Solution {
    public int countTriplets(int[] nums) {
        // cnt[mask] = 有多少个有序对 (i, j) 满足 nums[i] & nums[j] == mask。
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int a : nums) {
            for (int b : nums) {
                int mask = a & b;
                cnt.put(mask, cnt.getOrDefault(mask, 0) + 1);
            }
        }

        int answer = 0;
        for (int c : nums) {
            for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {
                // c 的每个 1 位都必须落在 mask 的 0 位上。
                if ((e.getKey() & c) == 0) {
                    answer += e.getValue();
                }
            }
        }
        return answer;
    }
}

func countTriplets(nums []int) int {
    // cnt[mask] = 有多少个有序对 (i, j) 满足 nums[i] & nums[j] == mask。
    cnt := make(map[int]int)
    for _, a := range nums {
        for _, b := range nums {
            cnt[a&b]++
        }
    }

    answer := 0
    for _, c := range nums {
        for mask, times := range cnt {
            // c 的每个 1 位都必须落在 mask 的 0 位上。
            if mask&c == 0 {
                answer += times
            }
        }
    }
    return answer
}

复杂度分析

时间复杂度：$O(n^2 + n \cdot U)$，其中 U 是不同按位与结果的数量，上界为 $2^{16} = 65536$。凭什么：阶段一是标准的双重循环共 $n^2$ 次哈希更新；阶段二外层 n 次、内层遍历表中全部键，键数受值域封顶。代入约束得 $10^6 + 1000 \times 65536 \approx 6.6 \times 10^7$，在时限内。

空间复杂度：$O(U)$，同样以 65536 为上界。凭什么：哈希表只存不同的 mask 值，与 $n^2$ 个有序对无关——归并正是这个解法压缩空间的地方；除此之外只有几个标量。

关键点总结

三元组统计题的通用降幂手法是「拆成两段 + 中间量归并」：先把前两维的组合结果按值归并成计数表，再让第三维去查表，把 $O(n^3)$ 降到 $O(n^2 + n \cdot U)$。454 题的四数相加用的是同一招。

归并能成立的前提是「后续判断只依赖中间量的值，不依赖它由谁产生」。动手前先确认这一点，否则合并会丢信息。

约束里出现「元素小于 $2^{16}$」这类具体值域时，几乎总是在提示中间量的取值空间有限，可以用值域当复杂度维度。

计数口径必须先读准：本题区分顺序且允许下标重合，所以两层循环都跑满 n；一旦题目改成 i < j < k，整套计数方式都要改，不能照抄。

a & b & c == 0 用结合律拆成 (a & b) & c == 0 是解法的支点；位运算题里，把条件重写成「先算一个中间掩码，再判相容」往往就能看见归并的机会。

面试视角：先报 $O(n^3)$ 及其为什么超时，再说「不同的 (i, j) 可能产生相同的 a & b」这个观察，最后给出两阶段方案并用约束里的 $2^{16}$ 解释为什么第二阶段可控。若被追问优化，可以提两条路：把哈希表换成长度 65536 的定长数组以去掉哈希开销；或者反过来对每个 c 枚举其补码的所有子掩码（子集枚举），把第二阶段变成 $O(n \cdot 3^{16} / 2^{16})$ 级别的操作。

易错点总结

错误写法：阶段一写成 for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) → 用例 [0,0,0] 中只统计了 3 个无序对，答案变成 9 而不是 27，因为题目区分顺序且允许下标重合。

错误写法：阶段二累加 1 而不是 times → 用例 [2,1,3] 中每个相容的 mask 只算一次，答案从 12 变成 7，丢掉了同一 mask 背后的多个有序对。

错误写法：Java 里条件写成 e.getKey() & c == 0 → & 优先级低于 ==，被解析成 key & (c == 0)，直接编译失败；必须写成 (e.getKey() & c) == 0。

错误写法：把条件写成 mask == 0 || c == 0 → 用例 [2,1,3] 中 mask = 2、c = 1 明明相容却被漏掉，答案从 12 降到 8。

错误写法：阶段一直接统计 a | b 或 a ^ b → 用例 [2,1,3] 中判据与题目条件不符，答案完全对不上；三元组条件是按位与，中间量也必须是按位与。

错误写法：先对 nums 去重再做两阶段 → 用例 [0,0,0] 去重后只剩一个 0，答案变成 1，而计数题的重复元素必须保留。

错误写法：把哈希表的键设成 (a, b) 组成的字符串或 a * 100000 + b → 用例 n = 1000 时键有 $10^6$ 个，归并失效，第二阶段退化成 $O(n^3)$ 并超时。

错误写法：阶段二内层遍历原数组的所有对而不是遍历计数表 → 用例 n = 1000 时等价于三重循环，$10^9$ 次运算超时。

错误写法：用 cnt.get(mask) 而不先判存在 → 用例中首次遇到某个 mask 时 Java 返回 null，自动拆箱抛空指针异常。

错误写法：答案变量声明为 short 或在中途做了乘法放大 → 用例 n = 1000 且元素多为 0 时答案接近 $10^9$，窄类型直接溢出成负数。

错误写法：认为 a & b & c == 0 等价于三个数中必有一个为 0 → 用例 [2,1,3] 中 2 & 1 & 3 = 0 而三个数都非零，这个误解会让答案严重偏小。

错误写法：为了「优化」在阶段一中跳过 a == b 的情形 → 用例 [0,0,0] 中 i == j 的组合被丢掉，答案从 27 降到 18。

相似题目

题目	难度	考察点
454. 四数相加 II	中等	同样把四层枚举拆成两两归并再查表，中间量是和而不是按位与掩码
1178. 猜字谜	困难	也把字符集压成 16 位以内的掩码，但匹配条件是子集包含，需枚举子掩码
421. 数组中两个数的最大异或值	中等	位运算配合字典树按位贪心，考的是逐位决策而非计数归并
477. 汉明距离总和	中等	按位独立拆解后统计每位的 0/1 个数相乘，是另一种把位维度分离的手法
15. 三数之和	中等	同为三元组统计，但要求下标严格递增且需去重，排序加双指针而非归并
78. 子集	中等	用二进制位表示选取状态，是理解「掩码即集合」这一映射的基础题
1442. 形成两个异或相等数组的三元组数目	中等	也是三元组计数加位运算，但靠前缀异或把条件化简为端点相等