How does the array scanning plus hash lookup pattern apply here?

Each domino is converted to a canonical form and stored in a hash map; scanning the array while updating counts allows direct pair calculation.

Can this approach handle very large arrays of dominoes?

Yes, because the solution is O(n) time with a small, bounded hash map, making it efficient even for large inputs.

Why do we need to normalize dominoes?

Normalization ensures that equivalent dominoes like [2,1] and [1,2] map to the same key, allowing correct counting of pairs.

What is the maximum number of unique domino keys we can have?

Since domino values are between 1 and 9, there are at most 45 unique normalized domino keys.

How do we count pairs without iterating all pairs?

Use the hash map counts: for each domino, add the current count of its normalized key to the total, capturing all previous equivalent dominoes efficiently.

#1128

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

等价多米诺骨牌对的数量

给你一组多米诺骨牌 dominoes 。形式上， dominoes[i] = [a, b] 与 dominoes[j] = [c, d] 等价当且仅当 ( a == c 且 b == d ) 或者 ( a == d 且 b == c ) 。即一张骨牌可以通过旋转 0 度或 180 度得到另一张多…

数组哈希表计数

题目描述

给你一组多米诺骨牌 dominoes 。

形式上，dominoes[i] = [a, b] 与 dominoes[j] = [c, d] 等价当且仅当 (a == c 且 b == d) 或者 (a == d 且 b == c) 。即一张骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌。

在 0 <= i < j < dominoes.length 的前提下，找出满足 dominoes[i] 和 dominoes[j] 等价的骨牌对 (i, j) 的数量。

示例 1：

输入：dominoes = [[1,2],[2,1],[3,4],[5,6]]
输出：1

示例 2：

输入：dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]]
输出：3

提示：

1 <= dominoes.length <= 4 * 10⁴
dominoes[i].length == 2
1 <= dominoes[i][j] <= 9

lightbulb

解题思路

方法一：计数

我们可以将每个多米诺骨牌的两个数字按照大小顺序拼接成一个两位数，这样就可以将等价的多米诺骨牌拼接成相同的两位数。例如，[1, 2] 和 [2, 1] 拼接成的两位数都是 12，[3, 4] 和 [4, 3] 拼接成的两位数都是 34。

然后我们遍历所有的多米诺骨牌，用一个哈希表或者一个长度为 $100$ 的数组 $cnt$ 记录每个两位数出现的次数。对于每个多米诺骨牌，我们拼接成的两位数为 $x$ ，那么答案就会增加 $cnt[x]$ ，接着我们将 $cnt[x]$ 的值加 $1$ 。继续遍历下一个多米诺骨牌，就可以统计出所有等价的多米诺骨牌对的数量。

时间复杂度 $O(n)$ ，空间复杂度 $O(C)$ 。其中 $n$ 是多米诺骨牌的数量，而 $C$ 是多米诺骨牌中拼接成的两位数的最大数量，即 $100$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        cnt = Counter()
        ans = 0
        for a, b in dominoes:
            x = a * 10 + b if a < b else b * 10 + a
            ans += cnt[x]
            cnt[x] += 1
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) because each domino is processed once, and hash map operations are O(1). Space complexity is O(1) in practice since there are at most 45 possible domino combinations, making the hash map size effectively constant.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Looks for hash-based counting for array elements
question_mark
Wants O(n) solution without nested loops
question_mark
Checks for canonical representation handling rotations

warning

常见陷阱

外企场景

error
Forgetting to normalize dominoes before hashing, leading to missed pairs
error
Using nested loops, causing O(n^2) time instead of O(n)
error
Not accounting for all previously seen equivalent dominoes correctly in the count

swap_horiz

进阶变体

外企场景

arrow_right_alt
Counting equivalent pairs with more than two elements per domino
arrow_right_alt
Finding the maximum number of equivalent domino groups instead of pairs
arrow_right_alt
Allowing domino values larger than single digits

help

常见问题

外企场景

继续练习

#1160 拼写单词 #1090 受标签影响的最大值 #1054 距离相等的条形码