0982. Triples with Bitwise AND Equal To Zero

题目信息

题号:

0982

难度:

Hard

主题:

数组、按位与、有序三元组计数

原题:

LeetCode 0982

重点:

统计有序下标三元组 (i, j, k),三个下标可以彼此相同;只要对应三个数的按位与结果为零就计入

题目重述

给定整数数组 nums。请统计有多少个有序下标三元组 (i, j, k) 满足 0 <= i, j, k < nums.length,并且 nums[i] & nums[j] & nums[k] == 0。

三个下标独立选择,可以出现 i == j、j == k 或三者全部相同。顺序不同的三元组属于不同方案,即 (i, j, k) 与 (j, i, k) 通常分别计数。

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

自建示例

两个数产生六个按位与为零的有序三元组:

输入:nums = [1,2]
输出:6
解释:总共有 2^3 = 8 个有序下标三元组。只有三个位置全选值 1 或全选值 2 时按位与非零,其余六个三元组都同时含 1 和 2,按位与为 0。

数组只有一个零:

输入:nums = [0]
输出:1
解释:唯一有序三元组是 (0,0,0),对应 0 & 0 & 0 = 0,因此计为一种。