What is the pattern used to solve the 'Finding 3-Digit Even Numbers' problem?

The problem follows a pattern of array scanning plus hash lookup to generate unique valid 3-digit even numbers.

How do I handle duplicates in the 'Finding 3-Digit Even Numbers' problem?

You can handle duplicates by using a hash set to store only unique combinations of valid 3-digit even numbers.

What should I do if the array contains leading zeros?

Make sure to avoid leading zeros when forming numbers by checking the first digit of each combination before adding it to the result.

Can I solve the 'Finding 3-Digit Even Numbers' problem without checking for even numbers?

No, the problem requires that all generated numbers must be even, so the last digit must be even for each valid combination.

What is the time complexity of the 'Finding 3-Digit Even Numbers' problem?

The time complexity is O(k * 10^k), where k is the number of digits, because you generate combinations and check each one for validity.

#2094

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

找出 3 位偶数

给你一个整数数组 digits ，其中每个元素是一个数字（ 0 - 9 ）。数组中可能存在重复元素。你需要找出所有满足下述条件且互不相同的整数：该整数由 digits 中的三个元素按任意顺序依次连接组成。该整数不含前导零该整数是一个偶数例如，给定的 digits 是 […

数组哈希表排序枚举

题目描述

给你一个整数数组 digits ，其中每个元素是一个数字（0 - 9）。数组中可能存在重复元素。

你需要找出所有满足下述条件且 互不相同 的整数：

该整数由 digits 中的三个元素按任意顺序 依次连接 组成。
该整数不含 前导零
该整数是一个偶数

例如，给定的 digits 是 [1, 2, 3] ，整数 132 和 312 满足上面列出的全部条件。

将找出的所有互不相同的整数按 递增顺序 排列，并以数组形式返回。

示例 1：

输入：digits = [2,1,3,0]
输出：[102,120,130,132,210,230,302,310,312,320]
解释：
所有满足题目条件的整数都在输出数组中列出。 
注意，答案数组中不含有 奇数 或带 前导零 的整数。

示例 2：

输入：digits = [2,2,8,8,2]
输出：[222,228,282,288,822,828,882]
解释：
同样的数字（0 - 9）在构造整数时可以重复多次，重复次数最多与其在 digits 中出现的次数一样。 
在这个例子中，数字 8 在构造 288、828 和 882 时都重复了两次。

示例 3：

输入：digits = [3,7,5]
输出：[]
解释：
使用给定的 digits 无法构造偶数。

提示：

3 <= digits.length <= 100
0 <= digits[i] <= 9

lightbulb

解题思路

方法一：计数 + 枚举

我们先统计 $\textit{digits}$ 中每个数字出现的次数，记录在数组或哈希表 $\textit{cnt}$ 中。

然后，我们在 $[100, 1000)$ 的范围内枚举所有的偶数，判断这个偶数的每一位数字是否都不超过 $\textit{cnt}$ 中对应的数字的次数。如果是，则将这个偶数加入答案数组中。

最后，返回答案数组。

时间复杂度 $O(k \times 10^k)$ ，其中 $k$ 是目标偶数的位数，本题中 $k = 3$ 。忽略答案的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        cnt = Counter(digits)
        ans = []
        for x in range(100, 1000, 2):
            cnt1 = Counter()
            y = x
            while y:
                y, v = divmod(y, 10)
                cnt1[v] += 1
            if all(cnt[i] >= cnt1[i] for i in range(10)):
                ans.append(x)
        return ans

speed

复杂度分析

指标	值
时间	O(k \cdot 10^k)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Checks understanding of array scanning for combinations.
question_mark
Evaluates use of hash sets for uniqueness and performance.
question_mark
Assesses handling of edge cases like leading zeros and no even numbers.

warning

常见陷阱

外企场景

error
Forgetting to handle leading zeros, which would result in invalid numbers.
error
Not using a hash set to store unique numbers, leading to repeated numbers in the result.
error
Overlooking the constraint that only even numbers should be generated.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Using larger arrays with more digits.
arrow_right_alt
Ensuring the solution works with arrays containing only odd digits.
arrow_right_alt
Optimizing the algorithm to handle larger inputs more efficiently.

help

常见问题

外企场景

继续练习

#2122 还原原数组 #2099 找到和最大的长度为 K 的子序列 #2135 统计追加字母可以获得的单词数