982. 按位与为零的三元组
1. 题目
982. 按位与为零的三元组
2. 解题思路
随机选择两个数，记录两个数的与结果。以及它的次数。
然后再遍历数组，用第三个数去与前两个数的结果，如果等于0，则满足条件。
3. 代码
3.1. 注意点
首先用简单的思路切入，map来存储数组中每两个数组进行&的结果，然后遍历数组用数组中的每一个数和另外两个数&的结果再进行& 看是不是等于0。
等于0则从map取出，另外两个数进行&后的值的数量加到结果上去。
上面这句话不好理解，我来举个例子：
假设数组为[2,1,3]，那么
- (i=0, j=0, k=1) : 2 & 2 & 1
- (i=0, j=1, k=0) : 2 & 1 & 2
- 。。。。。
可以看到这两种情况，i=0，k=1 &的结果为0，会被放到map，那么i=0，j=1 &的结果也是0，那么也会放到map，这个时候map中有个元素就是<0,2> ，代表两个元素进行&后结果为0的，有两对元素。
当第三轮遍历的时候，取nums中的数字去与另外两个数的&结果进行&运算，发现结果为0，但是整个数组中 另外两个数的&结果 为0，的数字有2对，所以结果应该是res +=map.get(另外两对数字的结果)。
上面的思路虽然简单，但是在PAT中会超时，那么用int[]来替代map优化时间复杂度
[!NOTE] 1、int数组的大小为什么是
2^16
[!NOTE] 2、bitCount每一位的含义是什么？
bitCount[0]代表两个数字&操作后结果为0的个数…以此类推
3.2. 完整代码
超时版本（容易理解）：
class Solution {public int countTriplets(int[] nums) {int count = 0;Map < Integer, Integer > map = new HashMap < > ();for (int i: nums) {for (int j: nums) {int count1 = map.getOrDefault(i & j, 0);map.put(i & j, count1 + 1);}}for (Integer num: map.keySet()) {for (int m: nums) {if ((m & num) == 0) {count += map.get(num);}}}return count;}
}
优化时间复杂度后的版本：
class Solution {public int countTriplets(int[] nums) {// 用于存储按位与结果的次数，数组长度为 65536，因为 int 是 16 位的二进制数int[] bitCount = new int[1 << 16]; // 2^16 = 65536int res = 0;// 预处理：计算所有两数的按位与结果，存储其出现的次数for (int i: nums) {for (int j: nums) {int andResult = i & j;bitCount[andResult] ++;}}// 再次遍历数组，查找哪些数与之前的按位与结果为0for (int num: nums) {for (int i = 0; i < bitCount.length; i++) {if ((num & i) == 0) {res += bitCount[i]; // 累加符合条件的次数}}}return res;}
}