位运算题目：按位与为零的三元组

题目

标题和出处

标题：按位与为零的三元组

出处：982. 按位与为零的三元组

难度

6 级

题目描述

要求

给定一个整数数组 $\text{nums}$，返回按位与三元组的数量。

一个按位与三元组是一个下标三元组 $\text{(i, j, k)}$，使得：

• $\text{0}\le \text{i}<\text{nums.length}$
• $\text{0}\le \text{j}<\text{nums.length}$
• $\text{0}\le \text{k}<\text{nums.length}$
• $\text{nums[i] \& nums[j] \& nums[k]}=\text{0}$，其中 $\text{\&}$ 表示按位与操作符

示例

示例 1：

输入：$\text{nums = [2,1,3]}$
输出：$\text{12}$
解释：我们可以选出如下 $\text{(i, j, k)}$ 三元组：
$\text{(i=0, j=0, k=1)}$：$\text{2 \& 2 \& 1}$
$\text{(i=0, j=1, k=0)}$：$\text{2 \& 1 \& 2}$
$\text{(i=0, j=1, k=1)}$：$\text{2 \& 1 \& 1}$
$\text{(i=0, j=1, k=2)}$：$\text{2 \& 1 \& 3}$
$\text{(i=0, j=2, k=1)}$：$\text{2 \& 3 \& 1}$
$\text{(i=1, j=0, k=0)}$：$\text{1 \& 2 \& 2}$
$\text{(i=1, j=0, k=1)}$：$\text{1 \& 2 \& 1}$
$\text{(i=1, j=0, k=2)}$：$\text{1 \& 2 \& 3}$
$\text{(i=1, j=1, k=0)}$：$\text{1 \& 1 \& 2}$
$\text{(i=1, j=2, k=0)}$：$\text{1 \& 3 \& 2}$
$\text{(i=2, j=0, k=1)}$：$\text{3 \& 2 \& 1}$
$\text{(i=2, j=1, k=0)}$：$\text{3 \& 1 \& 2}$

示例 2：

输入：$\text{nums = [0,0,0]}$
输出：$\text{27}$

数据范围

• $\text{1}\le \text{nums.length}\le \text{1000}$
• $\text{0}\le \text{nums[i]}<{\text{2}}^{\text{16}}$

解法

思路和算法

最直观的做法是使用三重循环遍历数组 $\text{nums}$ 计算按位与为零的三元组的数量，该做法的时间复杂度是 $O(n^3)$，需要优化。

以下用 $(a,b,c)$ 表示每个三元组中的三个整数，按照顺序依次是 $a$、$b$、$c$。

首先枚举所有可能的二元组 $(a,b)$，统计每个 $a\&b$ 的值的计数并使用哈希表记录，枚举结束后，哈希表中包含每个三元组中的前两个整数的排列以及计数。

然后枚举所有可能的 $c$。数组 $\text{nums}$ 中的每个整数都可以作为三元组中的 $c$，对于每个 $c$，如果哈希表中存在整数 $x$ 使得 $x\&c=0$，则存在两个整数 $a$ 和 $b$ 使得 $a\&b=x$，因此存在按位与为零的三元组 $(a,b,c)$，当 $c$ 固定时，按位与为零的三元组 $(a,b,c)$ 的数量是 $x$ 在哈希表中的计数。枚举结束后，即可得到按位与为零的三元组的数量。

实现方面，由于数组 $\text{nums}$ 中的所有整数都小于 $2^{16}$，任意两个整数的按位与结果也一定小于 $2^{16}$，因此可以使用数组代替哈希表，作为哈希表的数组的长度为数组 $\text{nums}$ 的最大值加 $1$。

代码

class Solution {public int countTriplets(int[] nums) {int count = 0;int maxNum = 0;for (int num : nums) {maxNum = Math.max(maxNum, num);}int[] map = new int[maxNum + 1];for (int num1 : nums) {for (int num2 : nums) {map[num1 & num2]++;}}for (int i = 0; i <= maxNum; i++) {if (map[i] != 0) {for (int num : nums) {if ((i & num) == 0) {count += map[i];}}}}return count;}
}

复杂度分析

• 时间复杂度：$O(n^2+nm)$，其中 $n$ 是数组 $\text{nums}$ 的长度，$m$ 是数组 $\text{nums}$ 的最大值。寻找数组 $\text{nums}$ 的最大值需要 $O(n)$ 的时间，枚举二元组需要 $O(n^2)$ 的时间，枚举三元组的最后一个数并计算按位与为零的三元组数量需要 $O(nm)$ 的时间，因此时间复杂度是 $O(n^2+nm)$。

• 空间复杂度：$O(m)$，其中 $m$ 是数组 $\text{nums}$ 的最大值。空间复杂度主要取决于哈希表，哈希表的大小是 $O(m)$。