leetcode 982

问题

Given an array of integers A, find the number of triples of indices (i, j, k) such that:

  • 0 <= i < A.length
  • 0 <= j < A.length
  • 0 <= k < A.length
  • A[i] & A[j] & A[k] == 0, where & represents the bitwise-AND operator.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input: [2,1,3]
Output: 12
Explanation: We could choose the following i, j, k triples:
(i=0, j=0, k=1) : 2 & 2 & 1
(i=0, j=1, k=0) : 2 & 1 & 2
(i=0, j=1, k=1) : 2 & 1 & 1
(i=0, j=1, k=2) : 2 & 1 & 3
(i=0, j=2, k=1) : 2 & 3 & 1
(i=1, j=0, k=0) : 1 & 2 & 2
(i=1, j=0, k=1) : 1 & 2 & 1
(i=1, j=0, k=2) : 1 & 2 & 3
(i=1, j=1, k=0) : 1 & 1 & 2
(i=1, j=2, k=0) : 1 & 3 & 2
(i=2, j=0, k=1) : 3 & 2 & 1
(i=2, j=1, k=0) : 3 & 1 & 2

Note:

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

分析

先预处理一下每两个数的按位与的结果，然后再遍历每一个数。时间复杂度$O(n^2+max(A)n)$ 或 $O(n^2+n2^{16})$

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 1024 ms
class Solution {
public:
    int countTriplets(vector<int>& A) {
        unordered_map<int,int> mp;
        for (int a: A)
            for (int b: A)
                mp[a&b]++;

        int ans = 0;
        for (int a: A) {
            for (auto it: mp) {
                if ((it.first & a) == 0)
                    ans += it.second;
            }
        }
        return ans;
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 112 ms   线性表的执行时间比hashmap的执行时间少了不少
class Solution {
public:
    int countTriplets(vector<int>& A) {
        int dp[1<<16] = {};
        for (int a: A) {
            for (int b: A) {
                dp[a&b]++;
            }
        }
        int ans = 0;
        for (int a: A) {
            for (int i = 0; i < (1<<16); ++i) {
                if ((i & a) == 0)
                    ans += dp[i];
            }
        }
        return ans;
    }
};