统计按位与结果大于K的数组对数量：能否实现优于O(N²)的复杂度？

你想到的预处理方案的合理性 #

两个数做&（按位与）操作有个基本性质：运算结果一定小于等于两个操作数中的任意一个。也就是说只要某个元素本身的值≤K，不管它和数组里哪个元素配对，最终的与结果都不可能比自身更大，自然也不可能超过K。
这一步过滤完全没有计算冗余，能把暴力循环的实际遍历规模压到最小，但本质上还是O(m²)的复杂度（m是过滤后剩余的元素个数），并没有从根本上解决暴力法的效率瓶颈。

这类问题的复杂度优化上限 #

对于带固定二进制位宽的位运算计数问题，当前已知的最优渐近复杂度是和二进制位长绑定的线性复杂度——也就是O(n * log(max_val))。对于常规的32位整数来说，log(max_val)就是固定的32，本质上是O(n)的线性量级。
这个复杂度已经是理论上的下限：毕竟至少要完整遍历一遍所有数组元素才能完成统计，不可能存在比线性复杂度更低的通用解法。

能不能用Trie、哈希表这类结构做优化 #

为什么没法直接照搬两数之和的哈希表思路 #

两数之和能用哈希表实现线性复杂度，核心是它的判断条件是精确匹配：需要找和当前数相加等于固定值的单个目标元素，哈希表O(1)查精确值的特性刚好适配。
但这道题的判断条件是“按位与结果大于K”，匹配的不是某一个确定值，而是满足位运算范围要求的一整个元素集合。哈希表没有办法对这种范围查询直接做O(1)计数，硬要套用的话就得枚举所有可能的目标值组合，枚举成本会呈指数级上升，反而不如更适配位运算特性的方案高效。

01 Trie 是这类问题的标准优化方案 #

基于二进制高位优先构建的01 Trie，刚好能适配“按位与结果大于K”的批量计数需求，实现逻辑也很直接：

• 从整数的最高位到最低位，把每个数的二进制位逐层插入Trie，每个节点记录当前子树一共存储了多少个数字。
• 遍历数组逐个处理元素时，拿着当前元素的二进制位，从Trie的根节点开始逐位查找，把Trie里所有和当前元素配对、按位与结果能大于K的元素总数累加起来：
  1. 遇到当前元素某一位是0的情况：不管Trie里对应分支存的是0还是1，和当前位做与的结果都是0。如果K在这一位的值是1，说明这一位的与结果已经比K小，后续不管低位怎么组合，整体与结果都不可能超过K，直接跳过这部分的计数；如果K这一位是0，说明这一位的结果和K持平，继续往下走匹配即可。
  2. 遇到当前元素某一位是1的情况：如果Trie对应分支存的位也是1，那这一位的与结果就是1。如果K在这一位的值是0，说明这一位的结果已经比K大，后续不管低位怎么组合，整体与结果都一定大于K，直接把这个子树存储的所有元素数全部计入结果，再继续走逐位匹配的分支找刚好持平的组合；如果K这一位是1，那这一位的结果要和K持平才有机会后续超过阈值，就只往Trie中存1的分支继续走就行。
     这个方案每个数的插入、查找都是固定的32步（对应32位整数的位宽），整体下来是O(n*32)的线性复杂度，哪怕不做你之前想到的元素过滤，也能高效跑完。

实际选型的小建议 #

如果遇到K很小、过滤后剩下的元素个数m远小于n的场景，哪怕用之前的暴力循环，因为实际遍历的规模极小，运行速度大概率比带常数 overhead 的Trie方案还快。但从渐近复杂度的角度，Trie方案是这类问题能摸到的优化天花板，不存在更优的通用复杂度了。

内容的提问来源于stack exchange，提问作者yozaam