What is the main pattern used in Triples with Bitwise AND Equal To Zero?

The core pattern is array scanning combined with hash table lookups to efficiently count valid AND triples.

Can indices repeat in valid triples?

Yes, i, j, and k can be the same index, and all combinations must be counted.

Why not just use a triple nested loop?

Triple nested loops have O(n^3) time complexity, which is too slow for arrays up to length 1000.

How does the bitmask optimization improve performance?

It uses the 2^16 value constraint to precompute counts of masks and sum compatible combinations, reducing redundant computation.

What is a common pitfall when implementing this problem?

A frequent mistake is ignoring repeated indices or overcounting pairs without considering zero AND conditions, leading to incorrect totals.

#982

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

按位与为零的三元组

给你一个整数数组 nums ，返回其中按位与三元组的数目。按位与三元组是由下标 (i, j, k) 组成的三元组，并满足下述全部条件： 0 0 0 nums[i] & nums[j] & nums[k] == 0 ，其中 & 表示按位与运算符。示例 1：输入： nums = [2,1,3…

数组哈希表位运算

题目描述

给你一个整数数组 nums ，返回其中 按位与三元组 的数目。

按位与三元组 是由下标 (i, j, k) 组成的三元组，并满足下述全部条件：

0 <= i < nums.length
0 <= j < nums.length
0 <= k < nums.length
nums[i] & nums[j] & nums[k] == 0 ，其中 & 表示按位与运算符。

示例 1：

输入：nums = [2,1,3]
输出：12
解释：可以选出如下 i, j, k 三元组：
(i=0, j=0, k=1) : 2 & 2 & 1
(i=0, j=1, k=0) : 2 & 1 & 2
(i=0, j=1, k=1) : 2 & 1 & 1
(i=0, j=1, k=2) : 2 & 1 & 3
(i=0, j=2, k=1) : 2 & 3 & 1
(i=1, j=0, k=0) : 1 & 2 & 2
(i=1, j=0, k=1) : 1 & 2 & 1
(i=1, j=0, k=2) : 1 & 2 & 3
(i=1, j=1, k=0) : 1 & 1 & 2
(i=1, j=2, k=0) : 1 & 3 & 2
(i=2, j=0, k=1) : 3 & 2 & 1
(i=2, j=1, k=0) : 3 & 1 & 2

示例 2：

输入：nums = [0,0,0]
输出：27

提示：

1 <= nums.length <= 1000
0 <= nums[i] < 2¹⁶

lightbulb

解题思路

方法一：枚举 + 计数

我们可以先枚举任意两个数 $x$ 和 $y$ ，用哈希表或数组 $cnt$ 统计它们的按位与结果 $x \& y$ 出现的次数。

然后我们枚举 $x$ 和 $y$ 的按位与结果 $xy$ ，再枚举 $z$ ，如果 $xy \& z = 0$ ，则将 $cnt[xy]$ 的值加入答案。

最后返回答案即可。

时间复杂度 $O(n^2 + n \times M)$ ，空间复杂度 $O(M)$ ，其中 $n$ 是数组 $nums$ 的长度；而 $M$ 是数组 $nums$ 中的最大值，本题中 $M \leq 2^{16}$ 。

1

2

3

4

5

class Solution:
    def countTriplets(self, nums: List[int]) -> int:
        cnt = Counter(x & y for x in nums for y in nums)
        return sum(v for xy, v in cnt.items() for z in nums if xy & z == 0)

speed

复杂度分析

指标	值
时间	complexity depends on the approach: brute force is O(n^3), hash map pairwise computation is O(n^2 + n*2^16) in worst case, and bitmask optimization leverages the 2^16 bound to stay efficient. Space complexity is O(n^2) for pairwise storage or O(2^16) for bitmask counts.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate immediately considers the high n^3 brute force and mentions performance issues.
question_mark
Candidate references bit manipulation and hash tables to reduce redundant computation.
question_mark
Candidate evaluates value constraints to optimize for possible masks and avoids unnecessary nested loops.

warning

常见陷阱

外企场景

error
Attempting direct triple nested loops on large arrays, causing TLE.
error
Forgetting that indices can repeat, leading to undercounting.
error
Ignoring the 2^16 constraint, missing bitmask-based optimizations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count quadruples with bitwise AND zero instead of triples.
arrow_right_alt
Return all valid triples instead of just the count.
arrow_right_alt
Modify to count AND triples for a target value other than zero.

help

常见问题

外企场景

继续练习

#996 平方数组的数目 #957 N 天后的牢房 #1177 构建回文串检测