982. Triples with Bitwise AND Equal To Zero

题解

由于数组长度是1000，所以不能用n^3的算法。
因此考虑枚举两维。可以先将i & j的结果存到数组中，然后再进行k和 i& j结果的对比。
最终的复杂度是1000 * 65556的复杂度。

代码

  1. class Solution {
  2. public:
  3.     int countTriplets(vector<int>& nums) {
  4.         vector<int> ij(1 << 16, 0);
  5.         for (int i = 0; i < nums.size(); i ++) {
  6.             for (int j = 0; j < nums.size(); j ++) {
  7.                 ij[nums[i] & nums[j]] ++;
  8.             }
  9.         }
  11.         int res = 0;
  12.         for (int k = 0; k < nums.size(); k ++) {
  13.             for (int i = 0; i < 1 << 16; i ++) {
  14.                 // 这里需要区分优先级， &的优先级比==低
  15.                 if ((nums[k] & i) == 0) {
  16.                     res += ij[i];
  17.                 }
  18.             }
  19.         }
  20.         return res;
  21.     }
  22. };