class Solution {
public:
int countTriplets(vector<int>& nums) {
}
};
982. 按位与为零的三元组
给你一个整数数组 nums ，返回其中 按位与三元组 的数目。
按位与三元组 是由下标 (i, j, k) 组成的三元组，并满足下述全部条件：
0 <= i < nums.length0 <= j < nums.length0 <= k < nums.lengthnums[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 <= 10000 <= nums[i] < 216原站题解
java 解法, 执行用时: 5 ms, 内存消耗: 41 MB, 提交时间: 2023-03-04 17:55:00
class Solution {
public int countTriplets(int[] nums) {
int u = 1;
for (int x : nums)
while (u <= x)
u <<= 1;
int[] cnt = new int[u];
cnt[0] = nums.length; // 直接统计空集
for (int m : nums) {
m ^= u - 1;
for (int s = m; s > 0; s = (s - 1) & m) // 枚举 m 的非空子集
++cnt[s];
}
int ans = 0;
for (int x : nums)
for (int y : nums)
ans += cnt[x & y];
return ans;
}
}
java 解法, 执行用时: 6 ms, 内存消耗: 40.9 MB, 提交时间: 2023-03-04 17:54:48
class Solution {
public int countTriplets(int[] nums) {
int[] cnt = new int[1 << 16];
cnt[0] = nums.length; // 直接统计空集
for (int m : nums) {
m ^= 0xffff;
for (int s = m; s > 0; s = (s - 1) & m) // 枚举 m 的非空子集
++cnt[s];
}
int ans = 0;
for (int x : nums)
for (int y : nums)
ans += cnt[x & y];
return ans;
}
}
golang 解法, 执行用时: 4 ms, 内存消耗: 5.7 MB, 提交时间: 2023-03-04 17:54:26
func countTriplets(nums []int) (ans int) {
u := 1
for _, x := range nums {
for u <= x {
u <<= 1
}
}
cnt := make([]int, u)
cnt[0] = len(nums) // 直接统计空集
for _, m := range nums {
m ^= u - 1
for s := m; s > 0; s = (s - 1) & m { // 枚举 m 的非空子集
cnt[s]++
}
}
for _, x := range nums {
for _, y := range nums {
ans += cnt[x&y]
}
}
return
}
golang 解法, 执行用时: 8 ms, 内存消耗: 2.5 MB, 提交时间: 2023-03-04 17:54:14
func countTriplets(nums []int) (ans int) {
cnt := [1 << 16]int{len(nums)} // 直接统计空集
for _, m := range nums {
m ^= 0xffff
for s := m; s > 0; s = (s - 1) & m { // 枚举 m 的非空子集
cnt[s]++
}
}
for _, x := range nums {
for _, y := range nums {
ans += cnt[x&y]
}
}
return
}
python3 解法, 执行用时: 280 ms, 内存消耗: 15.5 MB, 提交时间: 2023-03-04 17:53:52
class Solution:
def countTriplets(self, nums: List[int]) -> int:
u = 1
for x in nums:
while u <= x:
u <<= 1
cnt = [0] * u
cnt[0] = len(nums) # 直接统计空集
for m in nums:
m ^= u - 1
s = m
while s: # 枚举 m 的非空子集
cnt[s] += 1
s = (s - 1) & m
return sum(cnt[x & y] for x in nums for y in nums)
python3 解法, 执行用时: 368 ms, 内存消耗: 15.5 MB, 提交时间: 2023-03-04 17:53:40
class Solution:
def countTriplets(self, nums: List[int]) -> int:
cnt = [0] * (1 << 16)
cnt[0] = len(nums) # 直接统计空集
for m in nums:
m ^= 0xffff
s = m
while s: # 枚举 m 的非空子集
cnt[s] += 1
s = (s - 1) & m
return sum(cnt[x & y] for x in nums for y in nums)
golang 解法, 执行用时: 116 ms, 内存消耗: 3 MB, 提交时间: 2023-03-04 17:50:16
func countTriplets(nums []int) (ans int) {
cnt := [1 << 16]int{}
for _, x := range nums {
for _, y := range nums {
cnt[x&y]++
}
}
for x, c := range cnt {
for _, y := range nums {
if x&y == 0 {
ans += c
}
}
}
return
}
cpp 解法, 执行用时: 56 ms, 内存消耗: 7 MB, 提交时间: 2023-03-04 17:49:57
class Solution {
public:
int countTriplets(vector<int> &nums) {
int cnt[1 << 16]{};
for (int x : nums)
for (int y : nums)
++cnt[x & y];
int ans = 0;
for (int x : nums)
for (int y = 0; y < 1 << 16; ++y)
if ((x & y) == 0)
ans += cnt[y];
return ans;
}
};
java 解法, 执行用时: 112 ms, 内存消耗: 41.3 MB, 提交时间: 2023-03-04 17:49:43
class Solution {
public int countTriplets(int[] nums) {
int[] cnt = new int[1 << 16];
for (int x : nums)
for (int y : nums)
++cnt[x & y];
int ans = 0;
for (int x : nums)
for (int y = 0; y < 1 << 16; ++y)
if ((x & y) == 0)
ans += cnt[y];
return ans;
}
}
python3 解法, 执行用时: 2444 ms, 内存消耗: 18.4 MB, 提交时间: 2023-03-04 17:49:22
class Solution:
def countTriplets(self, nums: List[int]) -> int:
cnt = Counter(x & y for x in nums for y in nums)
return sum(c for x, c in cnt.items() for y in nums if x & y == 0)