【leetcode】982. Triples with Bitwise AND Equal To Zero

题目如下：

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:

Input: [2,1,3]
Output: 12 Explanation: We could choose the following i,k triples: (i=0,j=0,k=1) : 2 & 2 & 1 (i=0,j=1,k=0) : 2 & 1 & 2 (i=0,k=1) : 2 & 1 & 1 (i=0,k=2) : 2 & 1 & 3 (i=0,j=2,k=1) : 2 & 3 & 1 (i=1,k=0) : 1 & 2 & 2 (i=1,k=1) : 1 & 2 & 1 (i=1,k=2) : 1 & 2 & 3 (i=1,k=0) : 1 & 1 & 2 (i=1,k=0) : 1 & 3 & 2 (i=2,k=1) : 3 & 2 & 1 (i=2,k=0) : 3 & 1 & 2 

?

Note:

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

解题思路：我的方法和 3Sum 题一样，就是先算出A中任意两个数的与值，然后再和A中所有值与操作判断是否为0，耗时3秒多。不管怎么样，至少通过了。

Runtime:?3772 ms,faster than?39.02%?of?Python?online submissions for?Triples with Bitwise AND Equal To Zero.

代码如下：

class Solution(object):
    def countTriplets(self,A):
        """
        :type A: List[int]
        :rtype: int
        """
        dic = {}
        for i in A:
            for j in A:
                v = i & j
                dic[v] = dic.setdefault(v,0) + 1
        res = 0
        for i in A:
            for k,v in dic.iteritems():
                if i & k == 0:
                    res += v
        return res