LeetCode（3）：982. 按位与为零的三元组_982.按位与为零的三元组 java

描述

`给定一个整数数组 A，找出索引为 (i, j, k) 的三元组，使得：

0 <= i < A.length
0 <= j < A.length
0 <= k < A.length
A[i] & A[j] & A[k] == 0，其中 & 表示按位与（AND）操作符。
 

示例：

输入：[2,1,3]
输出：12
解释：我们可以选出如下 i, j, k 三元组：
(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
 

提示：

1 <= A.length <= 1000
0 <= A[i] < 2^16
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

解法一：三重循环时间太长不予考虑

解法二：利用HashMap（借鉴别人）

public int countTriplets(int[] A) {
		Map<Integer,Integer> map = new HashMap();
		int result = 0;
		int n = A.length;
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
			{
				int temp = A[i]&A[j];
				map.put(temp, map.getOrDefault(temp, 0)+1);
				//getOrDefault如果存在这个key就用这个key对应的value，如果不存在就用第二个参数默认的
				
			}
		
		for(int key:map.keySet())
		{
			if(key == 0)
			{
				result += map.get(key)*n;
				continue;
			}
			
			for(int i=0;i<n;i++)
			{
				if((A[i]&key) == 0)
				{
					result += map.get(key);
				}
			}
			
		}
		return result;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

解法三：利用数组优化

public int test(int[] A)
	{
		 int ans = 0;
	        int[] map = new int[1<<16];
	        for(int i = 0; i < A.length; i++){
	            for(int j = 0; j < A.length; j++){
	                map[A[i] & A[j]]++;
	            }
	        }
	        
	        for(int i = 0; i < map.length; i++){
	            if(map[i] == 0) continue;
	            for(int j = 0; j < A.length; j++){
	                if((A[j] & i) == 0){
	                    ans += map[i];
	                }
	            }
	        }
	        return ans;


	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22