点击获取AI摘要

2094. 找出 3 位偶数 E

给你一个整数数组 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

问题分析

目标：从给定的整数数组 digits 中选出恰好 3 个元素，按任意顺序拼接成一个三位数，且该数不能有前导零，并且是偶数。所有满足条件且互不相同的数，按升序返回。

要考虑数字出现的次数限制——同一数字最多使用它在 digits 中出现的次数。
排除前导零（三位数的百位不能为 0）。
只保留偶数（个位为偶数）。
去重并按升序输出。

算法思路

统计频次
先用一个长度为 10 的数组 cnt 记录每个数字在 digits 中出现的次数，以便在选位时快速判断是否还有剩余。
三重枚举＋剪枝
- 枚举百位 h：只枚举 [1..9]，并且 cnt[h] > 0。
- 枚举十位 t：在剩余的数字中选（使用完百位后对应 cnt[h] 临时减 1），可以为 0–9，但要保证 cnt[t] > 0。
- 枚举个位 u：同理，在剩余中选，且 u 必须是偶数（0,2,4,6,8），并且 cnt[u] > 0。
- 每构造一个合法三位数 num = 100*h + 10*t + u，加入结果集合。
去重与排序
我们借助 Python 的 set 去重，最后将结果转为列表并排序。

时间复杂度

最坏情况三重枚举固定为 10 × 10 × 5 = 500 次尝试。
统计频次： $O(n)$ 。
总体： $O(n + 1)$ ，常数级别的三重循环 ⇒ 近似 $O(n)$ 。

代码实现

class Solution:
    def findEvenNumbers(self, digits: list[int]) -> list[int]:
        # 1. 统计每个数字的出现次数
        cnt = [0] * 10
        for d in digits:
            cnt[d] += 1

        res = set()
        # 2. 枚举三位数的各个位
        for h in range(1, 10):  # 百位不能为 0
            if cnt[h] == 0:
                continue
            cnt[h] -= 1

            for t in range(0, 10):  # 十位可以为 0
                if cnt[t] == 0:
                    continue
                cnt[t] -= 1

                for u in (0, 2, 4, 6, 8):  # 个位必须是偶数
                    if cnt[u] > 0:
                        num = 100 * h + 10 * t + u
                        res.add(num)

                cnt[t] += 1
            cnt[h] += 1

        # 3. 排序并返回
        return sorted(res)