2023.3.4Leecode982按位与为零的三元组

题目的要求

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

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

0 <= i < nums.length
0 <= j < nums.length
0 <= k < nums.length
nums[i] & nums[j] & nums[k] == 0 ，其中 & 表示按位与运算符。

题目的实例2

输入：nums = [0,0,0]

输出：27

1 <= nums.length <= 1000
0 <= nums[i] < 2^16



思路：
1.枚举
我们正常的解法可能就需要用三重的for循环，时间复杂度是O(n^3).在这里我们可以先用双重for循环来遍历 nums[i]&nums[j]的值，将他们存入到hash表中
这里我们直接采用数组作为hash表，nums[i]<2^16次方，nums[i]&nums[j] < 2^16。数组的长度最大开2^16次方.然后我们在进行双重for循环，第一层for
循环是接着遍历数组，第二重for循环我们就直接枚举m,判断 nums[k]&m是否等于0，等于0就去hash表中查找m是否存在(枚举值是否是之前进入hash表的nums[i]
&nums[j]),时间复杂度为O(n^2+n*2^16)
代码如下（typescript）

 1 function countTriplets(nums: number[]): number {

 2     //枚举法

 3     //用map(Array)来存放I下标和J下标的&值，然后再用双重for循环，一个是Z下标，一个值用来枚举map , 时间复杂度是O(n^2+2^16*n)

 4     const map = new Array(1 << 16).fill(0)

 5     //往map(数组)中添加元素

 6     for(const i of nums) {

 7         for(const j of nums){

 8             map[i&j]++

 9         }

10     }

11     let sum:number = 0

12     //再用枚举获取数值

13     for(const x of nums){

14         for(let i:number = 0; i < (1<<16); i++) {

15             if(<number>(x & i) == 0) {

16                 sum += map[i]

17             }

18         }

19     }

20     return sum

22 };

优化

在思路1的基础上我们可以采用子集优化的方式,在第二次遍历数组的时候我们获取到nums[k],假设将nums[k]转换成二维数组 5 = (101) ，将数值为1的下标放入到集合中，也就是{1,3}，命名为集合A。nums[k]&m等于0就代表nums[k]代表的集合和m代表的集合没有交集,m是CuA的子集。这样我们就可以直接枚举CuA的子集来优化算法。在本题中Cu是2^16也就是{1,2,...,16}也就是0xffff.有了Cu，那么我们如果遍历CuA的子集m呢。我们可以直接通过 m = (m-1)&CuA的写法来，一般来说是将m-1然后和CuA相与，如果结果是m-1代表它就是CuA的子集。(m-1)&CuA的写法的思路是，m-1的子集就是m的子集，m-1就是把m的最右位的1变成0，把该1右侧的0变成1，这样可以直接通过 & CuA快速获取到下一个子集.已经清楚了如何快速获取子集，那么结束的条件是啥呢, 当m-1达到-1时，-1的二进制码全是1，这个时候和CuA相与结果就变成了CuA，所以当m&CuA = CuA的时候就代表结束了这次操作

代码(typescript)

function countTriplets(nums: number[]): number {

    //枚举法

    const map = new Array(1 << 16).fill(0)

    //往map(数组)中添加元素

    for(const i of nums) {

        for(const j of nums){

            map[i&j]++

        }

    }

    let sum:number = 0

    for(let x of nums){

        //获取亦或值
　　　　　　

        x ^= 0xffff

        let mid = x

        do{

            sum += map[mid]

            mid = (mid-1) & x

        }while(mid != x)

    }

    return sum

};

巴特西

2023.3.4Leecode982按位与为零的三元组

最新文章

热门文章