LeetCode 题解工作台
能否连接形成数组
给你一个整数数组 arr ，数组中的每个整数 互不相同 。另有一个由整数数组构成的数组 pieces ，其中的整数也 互不相同 。请你以 任意顺序 连接 pieces 中的数组以形成 arr 。但是， 不允许 对每个数组 pieces[i] 中的整数重新排序。 如果可以连接 pieces 中的数组形…
2
题型
7
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
遍历 `arr`，在 `pieces` 中找到首元素等于当前 `arr[i]` 的数组项，如果找不到，直接返回 `false`。 如果找到了，我们记数组项为 `pieces[k]`，然后继续往后遍历 `arr[i]` 和 `pieces[k]`，直至 `pieces[k]` 遍历完或者元素不等。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 arr ，数组中的每个整数 互不相同 。另有一个由整数数组构成的数组 pieces，其中的整数也 互不相同 。请你以 任意顺序 连接 pieces 中的数组以形成 arr 。但是，不允许 对每个数组 pieces[i] 中的整数重新排序。
如果可以连接 pieces 中的数组形成 arr ，返回 true ；否则，返回 false 。
示例 1：
输入：arr = [15,88], pieces = [[88],[15]] 输出：true 解释：依次连接[15]和[88]
示例 2：
输入：arr = [49,18,16], pieces = [[16,18,49]] 输出：false 解释：即便数字相符，也不能重新排列 pieces[0]
示例 3：
输入：arr = [91,4,64,78], pieces = [[78],[4,64],[91]] 输出：true 解释：依次连接[91]、[4,64]和[78]
提示：
1 <= pieces.length <= arr.length <= 100sum(pieces[i].length) == arr.length1 <= pieces[i].length <= arr.length1 <= arr[i], pieces[i][j] <= 100arr中的整数 互不相同pieces中的整数 互不相同（也就是说，如果将pieces扁平化成一维数组，数组中的所有整数互不相同）
解题思路
方法一：暴力枚举
遍历 arr，在 pieces 中找到首元素等于当前 arr[i] 的数组项，如果找不到，直接返回 false。
如果找到了，我们记数组项为 pieces[k]，然后继续往后遍历 arr[i] 和 pieces[k]，直至 pieces[k] 遍历完或者元素不等。
遍历结束，返回 true。
class Solution:
def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:
i = 0
while i < len(arr):
k = 0
while k < len(pieces) and pieces[k][0] != arr[i]:
k += 1
if k == len(pieces):
return False
j = 0
while j < len(pieces[k]) and arr[i] == pieces[k][j]:
i, j = i + 1, j + 1
return True
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) where n is the length of arr, since each element is scanned once and hash lookups are constant time. Space complexity is O(m) where m is the number of pieces, to store the hash map of first elements to subarrays. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Checks if you recognize that distinct integers allow direct mapping without ambiguity.
- question_mark
Wants to see efficient scanning without nested loops over all pieces.
- question_mark
Observes if you handle unmatched segments and return false promptly.
常见陷阱
外企场景- error
Attempting to reorder integers within a piece, which violates the problem constraints.
- error
Scanning arr without using a hash map, resulting in unnecessary nested iteration and O(n*m) complexity.
- error
Failing to handle cases where a piece starts correctly but does not fully match the segment in arr.
进阶变体
外企场景- arrow_right_alt
Allow pieces to contain duplicate integers, requiring frequency checks rather than direct mapping.
- arrow_right_alt
Use a version where arr may contain repeated elements and pieces may need multiple concatenations.
- arrow_right_alt
Require reconstruction using the minimal number of pieces concatenations to form arr.