深圳安嘉建设有限公司网站,网站建设登录注册怎么做,公众号中微网站开发,网站如何做企业电子宣传册按位与为零的三元组
题目描述
给你一个整数数组 nums #xff0c;返回其中 按位与三元组 的数目。
按位与三元组 是由下标 (i, j, k) 组成的三元组#xff0c;并满足下述全部条件#xff1a;
0 i nums.length 0 j nums.length 0 k nums.l…按位与为零的三元组
题目描述
给你一个整数数组 nums 返回其中 按位与三元组 的数目。
按位与三元组 是由下标 (i, j, k) 组成的三元组并满足下述全部条件
0 i nums.length 0 j nums.length 0 k nums.length nums[i] nums[j] nums[k] 0 其中 表示按位与运算符。
样例
样例输入 nums [2,1,3] nums [0,0,0] 样例输出 12 解释可以选出如下 i, j, k 三元组 (i0, j0, k1) : 2 2 1 (i0, j1, k0) : 2 1 2 (i0, j1, k1) : 2 1 1 (i0, j1, k2) : 2 1 3 (i0, j2, k1) : 2 3 1 (i1, j0, k0) : 1 2 2 (i1, j0, k1) : 1 2 1 (i1, j0, k2) : 1 2 3 (i1, j1, k0) : 1 1 2 (i1, j2, k0) : 1 3 2 (i2, j0, k1) : 3 2 1 (i2, j1, k0) : 3 1 2 27 提示
1nums.length10001 nums.length 10001nums.length10000nums[i]2160 nums[i] 2^160nums[i]216
思路
数据范围不大 但肯定不能纯暴力的枚举三元组但可以类似使用两数之和的优化技巧优化时间复杂度。就感觉很微妙。不知如何形容。
代码实现
// 这次代码好有意思写的和python似的。
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)// (x y)一定得加括号if((x y) 0) ans cnt[y];return ans;}
}
