LeetCode 1640. 能否连接形成数组

2023-10-15 HGNULB 约 8 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 1640. 能否连接形成数组

题意分析

给一个目标数组 arr 和若干个小数组 pieces。允许任意调整 pieces 之间的先后顺序，但每个 piece 内部的元素顺序必须原样保留，问能不能把它们首尾相接拼成 arr。

题面里藏着一条决定性的信息：arr 中的整数互不相同，pieces 中的整数也互不相同，而且两边是同一个集合。「互不相同」意味着任意一个数值在整张拼图里只出现一次，于是每个数值唯一地对应一个 piece，并且唯一地对应该 piece 中的一个下标。这条唯一性把「枚举 pieces 的排列」这种指数级搜索直接压成了确定性的匹配：arr[0] 是谁，第一块拼图就必须是谁，没有第二种选择。

另一条信息是数据规模——arr.length 与 pieces.length 都不超过 100，元素值域是 1 到 100。值域这么小、总量这么少，说明出题人期待的是一遍扫描就能定论的写法，而不是回溯。

需要留意的边界是：某个 piece 的首元素在 arr 中根本不存在；某个 piece 的首元素能对上，但后续元素对不上；以及一块 piece 从 arr 的末尾附近开始、长度超出了 arr 的剩余部分。这三种都必须判成拼不出来。

由于两边元素集合相同、总长度相同，只要每一步都能严丝合缝地贴上去，扫到末尾就一定成立，不需要额外校验「是否所有 piece 都被用过」。

解法：映射首元素匹配

核心思路

最直白的做法是枚举 pieces 的全排列再拼接比对，复杂度 $O(m! \cdot n)$，pieces 稍多一点就完全跑不动。瓶颈在于「不知道下一块该放谁」，于是只能盲目试。

观察点在于：一旦确定了拼接位置 i，那么放在这里的 piece 的第一个元素必然等于 arr[i]。而元素互不相同保证了以 arr[i] 开头的 piece 至多只有一个。所以「下一块该放谁」根本不需要猜——它被 arr[i] 唯一确定了。

由此建立映射 first → piece，把「找下一块」从搜索变成一次 $O(1)$ 查表。

循环不变量：扫描指针 i 之前的 arr[0..i-1] 已经被若干块完整的 piece 无缝覆盖，且这种覆盖方式是唯一可能的。每一轮要么把 arr[i] 开头的那块 piece 整体贴上去、令 i 前进该 piece 的长度，从而维持不变量；要么发现贴不上，此时由唯一性可知不存在任何其他拼法，直接判负。

若循环走到末尾，选中的各块按顺序拼接后逐位等于 arr，所以返回真必然正确。反过来，若存在合法拼法，它在位置 i 使用的块必然以 arr[i] 开头；映射中的候选唯一，算法每轮都会选中同一块，因此不会错过任何可行方案。

解题步骤

先把 pieces 灌进映射表，键取 piece[0]，值取整块 piece。之所以只用首元素作键，是因为拼接时唯一的决策点就是「这个位置该由哪块开头」；用其他元素作键无法回答这个问题。

令 i = 0，进入循环，条件是 i < arr.length。用「还没覆盖完」而不是「piece 还没用完」作循环条件，是因为长度相同这一前提让前者必然蕴含后者，少维护一个计数器。

查表取出以 arr[i] 开头的 piece。查不到就说明 arr[i] 这个位置无块可放，返回 false。

逐位比对该 piece 与 arr 从 i 开始的一段。比对时必须同时检查 i + j 是否越界：piece 可能比 arr 的剩余长度还长，不检查就会数组越界而不是返回 false。任何一位不等也立即返回 false——因为这块是唯一候选，它对不上就再无退路。

把 i 前进整块 piece 的长度，而不是前进 1。这一步是「整块贴上去」的具体体现，也是不变量得以维持的原因。

循环正常结束返回 true。

以 arr = [91, 4, 64, 78]、pieces = [[78], [4, 64], [91]] 走一遍。建表后得到 78 → [78]、4 → [4, 64]、91 → [91]。i = 0：arr[0] = 91，查到 [91]，逐位比对 arr[0] = 91 相等，i 前进 1 变成 1。i = 1：arr[1] = 4，查到 [4, 64]，比对 arr[1] = 4、arr[2] = 64 都相等，i 前进 2 变成 3。i = 3：arr[3] = 78，查到 [78]，比对相等，i 前进 1 变成 4。循环条件不再满足，返回 true。

反例 arr = [1, 2, 3]、pieces = [[2], [1, 3]] 中，位置 0 唯一候选是 [1,3]，但第二项与 arr[1] = 2 不同，立即返回 false。唯一候选失配后不需要回溯。

代码实现

import java.util.HashMap;
import java.util.Map;

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 是 piece 数量。建表扫描 k 个首元素；主循环中指针按块前进，每个目标位置最多比较一次。哈希查询按均摊 $O(1)$ 计。

空间复杂度：$O(k)$。映射只保存每块的首元素和对原 piece 的引用，不复制 piece 内容。

关键点总结

「元素互不相同」这类唯一性约束是把搜索降级为确定性匹配的钥匙。读题时看到「distinct」就要立刻想：它让哪个决策从多选变成了单选。

用「决策点上唯一可判别的特征」作哈希键。这里决策点是拼接起始位置，能判别的特征就是首元素，所以键选 piece[0] 而不是别的。

指针按整块长度跳跃而不是逐个前进，是「整体匹配」类问题的通用写法，也天然保证了 piece 内部顺序不被破坏。

越界判断必须写在取值之前，短路顺序本身就是正确性的一部分。

面试视角：先说暴力全排列，再用唯一性论证「每一步只有一个候选，失败即全局失败」，最后给出 $O(n + k)$ 的扫描。若元素允许重复，首元素不再唯一定位 piece，才需要搜索或 DP。

易错点总结

错误写法：不判 i + j >= arr.length 就直接取 arr[i + j]。用例 arr = [1]、pieces = [[1, 2]] → 比对第二位时下标越界，Java 抛 ArrayIndexOutOfBoundsException、Go 触发 panic，而不是返回 false。

错误写法：把越界判断写在比值之后，如 arr[i + j] != p[j] || i + j >= arr.length。同样是 arr = [1]、pieces = [[1, 2]] → 或运算左边先求值就已经越界，短路根本没机会生效，照样崩溃。

错误写法：内层比对通过后写成 i++。用例 arr = [91, 4, 64, 78]、pieces = [[78], [4, 64], [91]] → 贴完 [4, 64] 后 i 只走到 2，接着拿 arr[2] = 64 去查表，映射表里没有键 64，返回 false，正确答案是 true。

错误写法：用 piece 的最后一个元素或全部元素作哈希键。用例 arr = [15, 88]、pieces = [[88], [15]] → 拼接时手上只有起始位置的值 15，用尾元素建的表查不到它，直接判负，正确答案是 true。

错误写法：只验证每块首元素，随后直接跳过整块。用例 arr = [1,2,3,4]、pieces = [[1,4],[3,2]] → 位置 0 和 2 都能找到对应首元素，错误实现会返回 true；但两块内部次序都与 arr 不符，正确答案是 false。

过度实现：额外维护 usedPieces。题目保证两边元素集合相同且元素唯一；一旦若干完整 piece 恰好覆盖 arr，就不可能还有未使用元素，额外集合不增加正确性。

错误写法：先按 pieces 的给定顺序依次往 arr 上贴。用例 arr = [91, 4, 64, 78]、pieces = [[78], [4, 64], [91]] → 第一块 [78] 与 arr[0] = 91 不符，返回 false，但题目允许重排 pieces，正确答案是 true。

错误写法：把 pieces 拍平成一个数组后排序再和排序后的 arr 比较。用例 arr = [1, 2, 3]、pieces = [[3, 1], [2]] → 两边排序后都是 [1, 2, 3]，返回 true，但 [3, 1] 内部顺序不可变，无论怎么摆都拼不出 [1, 2, 3]，正确答案是 false。

错误写法：查表失败时 continue 而不是 return false。用例 arr = [1, 3]、pieces = [[2], [1]] → i 停在 1 处永远查不到键 3，continue 让 i 不再变化，程序陷入死循环。

相似题目

题目	难度	考察点
1. 两数之和	简单	同样用「值 → 位置」的映射把一次查找压到 $O(1)$，但答案是下标对而非可行性判定
1768. 交替合并字符串	简单	拼接顺序被题目写死为交替，不需要决策，只考双指针边界
989. 数组形式的整数加法	简单	同样按位处理数组，但难点在进位向前传播而非块的定位
28. 找出字符串中第一个匹配项的下标	简单	整段比对的进阶版，失配后需要回退，无法像本题一样一失败就全局判负
1024. 视频拼接	中等	片段可重叠且候选不唯一，退化成区间贪心，选谁必须比较右端点
472. 连接词	困难	切分点不唯一，必须用字典树配合记忆化搜索，本题的唯一性优势在这里彻底消失
30. 串联所有单词的子串	困难	单词可重复且顺序任意，要用计数哈希表配合滑动窗口，而非首元素定位