LeetCode 1640. 能否连接形成数组
题目描述
题意分析
将
pieces中的完整数组块重新排列，连接后得到arr，每块内部的元素顺序必须保持。题目保证两边总长度相同，arr中元素互不相同，所有块合在一起的元素也互不相同。
解法：映射首元素匹配
核心思路
[!blue]
用i指向arr的第一个未匹配位置，已经经过的前缀都由完整块组成。下一块不能拆开，也不能调整内部顺序，因此它的首元素必须是arr[i]。所有块的元素互不相同，这样的块至多只有一块，可以预先建立“首元素到整块”的映射直接查找。找不到对应块就无解。找到后，必须逐项与
arr的当前位置比较；越过数组末尾或任一元素不同，也都无解，因为没有另一块可以替代这个被首元素唯一确定的选择。整块通过后，让i前进块长，继续保持前缀已经完整拼好的状态。无需额外记录块是否用过：若再次使用同一块，它的首元素就会在
arr中重复，违反元素唯一的前提。最终完整覆盖arr时，已用块总长度等于arr长度，而所有块的总长度也相同，因此没有剩余未用块。两边元素集合是否一致由实际匹配验证，不需要提前假定。
解题步骤
- 按每块首元素建立映射。
- 从 arr 的首个未匹配位置查找对应块。
- 逐项核对该块，缺失或不匹配就返回 false。
- 整块通过后前进对应长度，全部覆盖则返回 true。
代码实现
class Solution {
public boolean canFormArray(int[] arr, int[][] pieces) {
// 元素互不相同，首元素可以唯一标识一块 piece。
Map<Integer, int[]> map = new HashMap<>();
for (int[] p : pieces) {
map.put(p[0], p);
}
int i = 0;
while (i < arr.length) {
int[] p = map.get(arr[i]);
if (p == null) {
return false;
}
for (int j = 0; j < p.length; j++) {
// 先判越界再比值，防止 piece 长过 arr 的剩余部分。
if (i + j >= arr.length || arr[i + j] != p[j]) {
return false;
}
}
i += p.length;
}
return true;
}
}
func canFormArray(arr []int, pieces [][]int) bool {
// 元素互不相同，首元素可以唯一标识一块 piece。
m := make(map[int][]int)
for _, p := range pieces {
m[p[0]] = p
}
i := 0
for i < len(arr) {
p, ok := m[arr[i]]
if !ok {
return false
}
for j := 0; j < len(p); j++ {
// 先判越界再比值，防止 piece 长过 arr 的剩余部分。
if i+j >= len(arr) || arr[i+j] != p[j] {
return false
}
}
i += len(p)
}
return true
}
复杂度分析
- 时间复杂度：期望 $O(n+k)$，n 为 arr 长度，k 为块数。
- 空间复杂度：$O(k)$，映射只保存原块引用。
关键点总结
[!green]
- 首元素唯一，下一块无需枚举。
- 必须逐项检查块内部顺序。
- 完整块覆盖与总长度相同使额外已用集合不必要。
易错点总结
[!yellow]
- 只检查首元素就跳过整块：可能接受内部顺序错误的块。
- 通过一块后只前进一位：会把块内部元素误当成下一块起点。
- 按 pieces 输入顺序直接拼接：题目允许重排块。
- 排序两边后只比较元素集合：丢失块内不可变的顺序约束。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 139. 单词拆分 | 中等 | 原题词块前缀可能重叠而需要DP，本题数值唯一，可由当前首值定位唯一候选块再逐项核对。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！