【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, 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 <= A.length <= 1000

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

巴特西

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

最新文章

热门文章