LeetCode每日一题(982. Triples with Bitwise AND Equal To Zero)
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
Given an integer array nums, return the number of AND triples.
An AND triple is a triple of indices (i, j, k) such that:
0 <= i < nums.length
0 <= j < nums.length
0 <= k < nums.length
nums[i] & nums[j] & nums[k] == 0, where & represents the bitwise-AND operator.
Example 1:
Input: nums = [2,1,3]
Output: 12
Explanation: We could choose the following i, j, k triples:
(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
Example 2:
Input: nums = [0,0,0]
Output: 27
Constraints:
- 1 <= nums.length <= 1000
- 0 <= nums[i] < 2^16
因为 nums[i] < 2 ^ 16, 所以 nums[i] & nums[j] < 2 ^ 16, 我们用一个长度为 2 ^ 16 的数组 counts 来保存每个 nums[i] & nums[j]的出现频次假设 n 为 0 到 2^16 中的每个数字 如果 nums[i] & n == 0, 则 ans += counts[n]
impl Solution {
pub fn count_triplets(nums: Vec<i32>) -> i32 {
let mut counts = vec![0; 1 << 16];
for i in 0..nums.len() {
for j in 0..nums.len() {
counts[(nums[i] & nums[j]) as usize] += 1;
}
}
let mut ans = 0;
for i in 0..nums.len() {
for j in 0..1 << 16 {
if nums[i] & j == 0 {
ans += counts[j as usize];
}
}
}
ans
}
}