DeepSeek创始人梁文锋个人履历，真牛逼！

今天我们来聊个算法题——按位与为零的三元组。

题目大意就是，给你一个整数数组 nums，请你计算有多少个 (i, j, k) 组合 满足 nums[i] & nums[j] & nums[k] == 0，其中 i, j, k 是不同的索引。

看到 &（按位与），我下意识摸了摸我的 bitwise（比特运算）小册子，咱这可是一等一的程序员工具箱啊！但讲真，一开始看到这题，我也是懵的，毕竟直接三层 for 循环硬怼，这复杂度 O(n³) 直接超纲，面试官看了估计都要叹气。

既然暴力不行，那就得优化，核心思想是——“预处理+哈希优化”。

首先，我们知道：

1. **按位与 &**：只有在对应二进制位 都为 1 时，结果才是 1，否则就是 0。
2. 三元组 & 结果为 0，意味着 nums[i] & nums[j] & nums[k] 里每一位至少有一个 0，所以不能让 nums[i]、nums[j]、nums[k] 在相同的比特位上全是 1。

代码实现

import java.util.HashMap;
import java.util.Map;
public class ZeroBitwiseTriplets {
    public int countTriplets(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        // 统计所有两两与 (&) 结果的频率
        for (int x : nums) {
            for (int y : nums) {
                int andVal = x & y;
                freq.put(andVal, freq.getOrDefault(andVal, 0) + 1);
            }
        }
        int count = 0;
        // 遍历 nums，看看它能和哪些 (x & y) 的结果按位与为 0
        for (int z : nums) {
            for (int key : freq.keySet()) {
                if ((z & key) == 0) {
                    count += freq.get(key);
                }
            }
        }
        return count;
    }
    public static void main(String[] args) {
        ZeroBitwiseTriplets solution = new ZeroBitwiseTriplets();
        int[] nums = {2, 1, 3};
        System.out.println(solution.countTriplets(nums)); // 输出 12
    }
}

解释一下代码：

1. 预处理所有可能的二元组合 (nums[i] & nums[j])
   用 HashMap 存储所有 nums[i] & nums[j] 的结果及其出现次数，这样就能在后续查找 nums[k] & (nums[i] & nums[j]) == 0 时，直接用 O(1) 查询复杂度。
2. 遍历 nums，寻找与二元组合按位与为 0 的情况
   这个步骤就是“看看 nums[k] 能和多少个 (nums[i] & nums[j]) 组合成 0”。

这段代码的时间复杂度是 **O(n² + n * 2¹⁶) ≈ O(n²)**（考虑 nums[i] & nums[j] 结果最多是 2¹⁶ 种可能，实际远小于 n²），比起 O(n³) 好太多了！

进一步优化？

理论上可以用 位运算 + 计数优化 进一步缩小 HashMap 的大小，但这个思路已经是面试里很不错的优化方向了，面试官看到这段代码估计要点头了。

你可能踩的坑：

1. 如果直接暴力 O(n³)，数组稍微大点就 TLE（超时）了，所以一定要做预处理优化。
2. 注意 (x & y) & z == 0 其实是 (x & y) 作为整体去和 z 进行按位与，所以 HashMap 预处理时存的 key 不是 x 和 y，而是 x & y 的结果。

这个算法题挺有趣的，说到底就是把 暴力 变成 查表，一举降低时间复杂度。看到 & 这种位运算，一定要想到 预处理 + 哈希优化，这基本是面试里的黄金套路。

面试的时候要是你写出 O(n³) 的代码，面试官可能会说：“这不太行，能优化一下吗？”
如果你能写出 O(n²)，他可能会点头，说：“嗯，不错！”
要是你能进一步结合 bitmask（位掩码）优化，甚至还能把 HashMap 换成数组，时间复杂度进一步降低，那这轮面试你就赢了。

以上，希望大家都能拿下这个算法，别被 & 给按住摩擦了 😂！