LeetCode_位运算_困难_982.按位与为零的三元组

左手的ㄟ右手 2023-10-08 18:52 8阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个整数数组 nums ，返回其中按位与三元组的数目。

按位与三元组 是由下标 (i, j, k) 组成的三元组，并满足下述全部条件：

*  0 <= i < nums.length
 *  0 <= j < nums.length
 *  0 <= k < nums.length
 *  nums\[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 <= 1000  
0 <= nums\[i\] < 216

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/triples-with-bitwise-and-equal-to-zero

## 2.思路 ##

（1）枚举  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————枚举
    class Solution {
        
        public int countTriplets(int[] nums) {
        
            int[] cnt = new int[1 << 16];
            for (int num1 : nums) {
        
                for (int num2 : nums) {
        
                    cnt[num1 & num2]++;
                }
            }
            int res = 0;
            for (int num : nums) {
        
                for (int mask = 0; mask < (1 << 16); mask++) {
        
                    if ((num & mask) == 0) {
        
                        res += cnt[mask];
                    }
                }
            }
            return res;
        }
    }

[Link 1]: https://leetcode.cn/problems/triples-with-bitwise-and-equal-to-zero/solution/an-wei-yu-wei-ling-de-san-yuan-zu-by-lee-gjud/