题目
给你一个下标从 0 开始的正整数数组 nums 和一个正整数 k 。
如果满足下述条件，则数对 (num1, num2) 是 优质数对 ：
- num1 和 num2 都 在数组 nums 中存在。
- num1 OR num2 和 num1 AND num2 的二进制表示中值为 1 的位数之和大于等于 k ，其中 OR 是按位 或 操作，而 AND 是按位 与 操作。
返回 不同 优质数对的数目。
如果 a != c 或者 b != d ，则认为 (a, b) 和 (c, d) 是不同的两个数对。例如，(1, 2) 和 (2, 1) 不同。
注意：如果 num1 在数组中至少出现 一次 ，则满足 num1 == num2 的数对 (num1, num2) 也可以是优质数对。
示例 1：
输入：nums = [1,2,3,1], k = 3 输出：5 解释：有如下几个优质数对： - (3, 3)：(3 AND 3) 和 (3 OR 3) 的二进制表示都等于 (11) 。值为 1 的位数和等于 2 + 2 = 4 ，大于等于 k = 3 。 - (2, 3) 和 (3, 2)： (2 AND 3) 的二进制表示等于 (10) ，(2 OR 3) 的二进制表示等于 (11) 。值为 1 的位数和等于 1 + 2 = 3 。 - (1, 3) 和 (3, 1)： (1 AND 3) 的二进制表示等于 (01) ，(1 OR 3) 的二进制表示等于 (11) 。值为 1 的位数和等于 1 + 2 = 3 。 所以优质数对的数目是 5 。
示例 2：
输入：nums = [5,1,1], k = 10 输出：0 解释：该数组中不存在优质数对。
解题
方法一：等价转换
对于 x|y 和x&y中的 1，在同一个比特位上，如果都有 1，那这个 1 会被统计两次；如果一个为 1 另一个为 0，那这个 1 会被统计一次。
因此可以等价替换，与、或结果 的二进制位1的个数 和，就是两个数分别二进制位1的个数和。
class Solution { public: int getBits(int num){ int res=0; while(num){ res+=num&1; num>>=1; } return res; } long long countExcellentPairs(vector<int>& nums, int k) { //去重 sort(nums.begin(),nums.end()); nums.resize(unique(nums.begin(),nums.end())-nums.begin()); // nums.erase(unique(nums.begin(),nums.end()),nums.end()); //这两种都可以 int n=nums.size(); vector<int> cnt(64,0);//bits个数 ---->数量 for(int i=0;i<n;i++){ int bits=getBits(nums[i]);//求位1的数量 cnt[bits]++; } long long res=0; for(int i=1;i<=60;i++){ for(int j=1;j<=60;j++){ if(i+j>=k){ res+=1ll*cnt[i]*cnt[j]; } } } return res; } };
