按位与为零的三元组
难度:
标签:
题目描述
代码结果
运行时间: 191 ms, 内存: 16.6 MB
/*
* 题目思路:
* 1. 使用Java Streams来遍历所有可能的三元组 (i, j, k),并统计满足条件的数目。
* 2. 使用三重流分别遍历 i, j, k,并过滤 nums[i] & nums[j] & nums[k] == 0 的三元组。
*/
import java.util.stream.IntStream;
public class Solution {
public int countTriplets(int[] nums) {
int n = nums.length;
return (int) IntStream.range(0, n).boxed()
.flatMap(i -> IntStream.range(0, n).boxed()
.flatMap(j -> IntStream.range(0, n).boxed()
.filter(k -> (nums[i] & nums[j] & nums[k]) == 0)
)
).count();
}
}
解释
方法:
该题解采用了一种利用位运算的技巧来解决问题。首先找到数组中最大的数,并确定一个足够大的二进制数u,使得u是第一个大于数组中任何数的2的幂。这是为了方便后续的位运算。然后,使用一个数组cnt来记录每个可能的位模式(直到u-1)在数组中出现的次数。对于每个数m,在数组nums中,先计算其补码(m^=u-1),然后枚举其所有可能的非空子集,并更新cnt数组。最后,通过双重循环遍历nums数组,使用cnt数组计算所有满足条件的(i, j, k)三元组数量。具体来说,对于每对数x和y,寻找在cnt数组中x与y按位与的结果作为索引的值,这个值即表示有多少个k使得nums[k]与x和y按位与的结果为0。
时间复杂度:
O(n*u + n^2)
空间复杂度:
O(u + n)
代码细节讲解
🦆
为什么在确定变量u时选择它为大于数组中任何数的最小的2的幂,这个选择对算法的效率或结果有什么关键影响?
▷🦆
在计算每个数的补码时,使用了`m ^= u - 1`这个操作。这个补码在算法中扮演了什么角色,为什么需要这样计算补码?
▷🦆
算法中提到枚举每个数的所有非空子集,这一步是如何通过位操作实现的?具体的位操作`s = (s - 1) & m`如何保证枚举到所有子集?
▷