LeetCode 1640题解：哈希表与双指针实现数组匹配

1. 题目解析与核心思路

leetcode 1640题"能否连接形成数组"是一道考察数组操作能力的典型题目。题目要求判断给定的数组pieces是否能通过某种顺序拼接形成另一个数组arr。这道题在周赛中出现时，不少选手因为忽略边界条件而失分，实际上它考察的是对数组结构的深入理解和双指针技巧的灵活运用。

1.1 题目具体要求

给定一个由不同整数组成的数组arr和一个由若干子数组组成的数组pieces，需要判断是否可以通过按某种顺序连接pieces中的子数组来得到arr。连接意味着需要保持每个子数组中元素的原始顺序，但可以任意安排子数组的连接顺序。

例如：

• arr = [85], pieces = [[85]] → true
• arr = [15,88], pieces = [[88],[15]] → true
• arr = [49,18,16], pieces = [[16,18,49]] → false

1.2 关键解题思路

这道题的核心在于验证两个条件：

1. pieces中所有子数组的元素集合必须恰好覆盖arr的所有元素（无重复、无遗漏）
2. 每个子数组在arr中的出现必须是连续且顺序一致的

最直接的解法是使用哈希表记录每个子数组的首元素，然后遍历arr进行匹配。这种方法时间复杂度为O(n)，空间复杂度为O(m)，其中n是arr的长度，m是pieces中子数组的数量。

2. 最优解法实现与代码详解

2.1 哈希表+双指针解法

def canFormArray(arr, pieces): # 建立哈希映射：每个子数组的第一个元素 -> 整个子数组 piece_map = {p[0]: p for p in pieces} i = 0 n = len(arr) while i < n: if arr[i] not in piece_map: return False target_piece = piece_map[arr[i]] # 检查当前子数组是否匹配arr的相应部分 for num in target_piece: if i >= n or num != arr[i]: return False i += 1 return True

这个解法之所以能达到耗时100%和内存100%的优秀表现，关键在于：

1. 哈希表提供了O(1)时间复杂度的首元素查找
2. 双指针技巧(i)实现了对arr的单次线性遍历
3. 没有使用额外的数据结构存储中间结果

2.2 关键步骤解析

1. 哈希表构建：将每个子数组的首元素作为key，整个子数组作为value存入字典。这确保了我们可以快速定位到可能匹配的子数组。

2. 主循环逻辑：使用指针i遍历arr，对于每个arr[i]，在哈希表中查找匹配的子数组。如果没有找到，立即返回false。

3. 子数组验证：找到匹配的子数组后，逐个验证子数组元素是否与arr中接下来的元素一致。任何不匹配都会导致返回false。

4. 边界处理：在验证子数组时，需要检查i是否超出arr的边界，防止数组越界。

3. 复杂度分析与优化空间

3.1 时间复杂度分析

• 构建哈希表：O(m)，其中m是pieces中子数组的数量
• 主循环：最坏情况下需要遍历arr的所有元素，O(n)
• 总体时间复杂度：O(n + m)

由于题目保证arr和pieces中的所有元素都是唯一的，这保证了哈希表查找的高效性。

3.2 空间复杂度分析

• 哈希表存储：最坏情况下需要存储所有子数组，空间复杂度为O(m)
• 其他变量：常数空间
• 总体空间复杂度：O(m)

3.3 可能的优化方向

虽然当前解法已经非常高效，但在特定情况下还可以考虑：

1. 提前终止：如果pieces中所有子数组的总长度不等于arr的长度，可以直接返回false
2. 元素范围检查：如果arr和pieces的元素范围不一致，可以提前判断
3. 并行处理：对于超大数组，可以考虑分块处理（但leetcode环境下通常不需要）

4. 常见错误与调试技巧

4.1 典型错误模式

1. 忽略子数组顺序：只检查元素存在性而忽略了子数组内部的顺序要求

   • 错误示例：认为arr=[1,2,3], pieces=[[3],[2],[1]]应该返回true
   • 正确理解：子数组内部顺序必须保持，所以这个例子应该返回false

2. 边界条件处理不当：

   • 忘记检查子数组长度超过剩余arr长度的情况
   • 没有处理空数组的极端情况

3. 重复元素假设：

   • 错误地假设arr或pieces中可能有重复元素
   • 实际上题目明确说明所有整数都是不同的

4.2 调试技巧

1. 小规模测试用例：

   • 先测试单元素情况(arr=[1], pieces=[[1]])
   • 再测试顺序相反的情况(arr=[1,2], pieces=[[2],[1]])
   • 最后测试不匹配的情况(arr=[1,2,3], pieces=[[1],[3]])

2. 打印中间状态：

   print(f"i={i}, current num={arr[i]}, matched piece={piece_map.get(arr[i])}")

3. 边界检查断言：

   assert i < n, "Index out of bounds while checking piece"

5. 相似题目与扩展思考

5.1 leetcode相似题目推荐

1. 56. 合并区间：同样需要处理数组的连续性和排序问题
2. 763. 划分字母区间：基于特定条件划分数组的思路类似
3. 1574. 删除最短子数组使剩余数组有序：涉及数组连续子数组的处理

5.2 问题变种思考

1. 如果允许pieces中有重复元素：解法需要调整，可能需要记录每个子数组的出现次数
2. 如果arr中有重复元素：问题会变得复杂，可能需要回溯或动态规划的方法
3. 大规模数据下的处理：考虑分块处理或并行算法

5.3 实际应用场景

这种数组匹配问题在实际中有多种应用：

• 数据流重组：网络传输中数据包的顺序重组
• 基因组序列匹配：生物信息学中的序列比对
• 文件碎片重组：数字取证中的文件恢复

6. 语言特性与实现细节

6.1 Python实现注意事项

1. 字典的O(1)查找：Python中dict的实现保证了平均O(1)的查找时间
2. 列表切片的高开销：避免使用arr[i:i+len(piece)]这样的切片操作，它会产生新列表
3. 生成器表达式：对于超大数组，考虑使用生成器替代列表

6.2 Java实现要点

public boolean canFormArray(int[] arr, int[][] pieces) { Map<Integer, int[]> map = new HashMap<>(); for (int[] p : pieces) { map.put(p[0], p); } int i = 0; while (i < arr.length) { if (!map.containsKey(arr[i])) { return false; } int[] piece = map.get(arr[i]); for (int num : piece) { if (i >= arr.length || num != arr[i]) { return false; } i++; } } return true; }

Java实现需要注意：

1. 使用HashMap而不是TreeMap以保证O(1)查找
2. 数组长度使用length属性而不是方法调用
3. 自动装箱/拆箱对性能的影响可以忽略

6.3 C++实现优化

bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) { unordered_map<int, vector<int>> piece_map; for (auto& p : pieces) { piece_map[p[0]] = p; } int i = 0; while (i < arr.size()) { if (piece_map.find(arr[i]) == piece_map.end()) { return false; } auto& piece = piece_map[arr[i]]; for (int num : piece) { if (i >= arr.size() || num != arr[i]) { return false; } i++; } } return true; }

C++实现可以进一步优化：

1. 使用reserve预先分配哈希表空间
2. 传递参数时使用const引用避免拷贝
3. 考虑使用数组视图(range)来避免子数组拷贝

7. 测试用例设计与验证

7.1 必备测试用例集

1. 基础用例：

   • 输入：arr = [85], pieces = [[85]]
   • 预期：true

2. 顺序反转用例：

   • 输入：arr = [15,88], pieces = [[88],[15]]
   • 预期：true

3. 不匹配用例：

   • 输入：arr = [49,18,16], pieces = [[16,18,49]]
   • 预期：false

4. 多元素用例：

   • 输入：arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
   • 预期：true

5. 边界用例：

   • 输入：arr = [], pieces = []
   • 预期：true

7.2 压力测试用例

1. 大数组测试：

   • 生成10^5大小的arr和随机pieces
   • 验证算法在极限情况下的表现

2. 极端分布测试：

   • pieces中包含大量单元素子数组
   • pieces中包含少量但很长的子数组

7.3 测试自动化建议

import unittest class TestCanFormArray(unittest.TestCase): def test_cases(self): test_cases = [ ([85], [[85]], True), ([15,88], [[88],[15]], True), ([49,18,16], [[16,18,49]], False), ([91,4,64,78], [[78],[4,64],[91]], True), ([], [], True), ([1,2,3], [[1],[2]], False) ] for arr, pieces, expected in test_cases: with self.subTest(arr=arr, pieces=pieces): self.assertEqual(canFormArray(arr, pieces), expected) if __name__ == "__main__": unittest.main()

8. 算法竞赛中的应用技巧

8.1 周赛中的快速解题策略

1. 问题转化：将问题理解为"arr是否可以被pieces完全覆盖且不冲突"
2. 模式识别：识别出这是哈希表+线性扫描的经典模式
3. 简化思考：专注于首元素匹配这一关键点，避免过度设计

8.2 调试打印技巧

在竞赛环境中快速调试的打印策略：

def canFormArray(arr, pieces): print(f"Input arr: {arr}") print(f"Input pieces: {pieces}") piece_map = {p[0]: p for p in pieces} print(f"Piece map: {piece_map}") i = 0 n = len(arr) while i < n: print(f"Checking i={i}, arr[i]={arr[i]}") if arr[i] not in piece_map: print(f"Fail: {arr[i]} not in piece_map") return False target_piece = piece_map[arr[i]] print(f"Found matching piece: {target_piece}") for num in target_piece: if i >= n or num != arr[i]: print(f"Fail: piece element {num} != arr[{i}]={arr[i] if i<n else 'OOB'}") return False i += 1 print(f"Matched, new i={i}") print("All pieces matched successfully") return True

8.3 常见陷阱规避

1. 变量名混淆：在竞赛紧张环境下容易把i,j等指针混淆

   • 建议：使用更有意义的变量名，如current_idx

2. 边界条件遗漏：

   • 总是测试空输入情况
   • 检查循环条件是否包含等号

3. 过早优化：

   • 先写出清晰可读的解法
   • 确认正确后再考虑优化

9. 性能优化与进阶思考

9.1 极致优化方向

1. 内存优化：

   • 如果pieces很大，可以只存储子数组的起始索引和长度
   • 使用更紧凑的数据结构存储哈希表

2. 并行处理：

   • 将arr分块，并行验证各块
   • 需要处理块边界处的子数组跨越问题

3. 预处理优化：

   • 对pieces中子数组按长度排序
   • 优先匹配长子数组，减少匹配次数

9.2 算法扩展

1. 模糊匹配版本：

   • 允许少量不匹配的情况
   • 使用动态规划计算最小编辑距离

2. 多序列匹配：

   • 同时匹配多个arr序列
   • 应用在生物信息学的多序列比对中

3. 流式处理版本：

   • arr以数据流形式输入
   • 有限内存下的处理算法

9.3 数学性质分析

1. 排列组合角度：

   • 计算所有可能的pieces排列组合
   • 验证是否存在与arr匹配的组合

2. 图论建模：

   • 将子数组看作图中的节点
   • 边表示可以相邻连接的子数组
   • 问题转化为路径存在性问题

3. 字符串匹配视角：

   • 将数组转化为字符串
   • 使用KMP等字符串匹配算法

10. 实际工程应用与总结

10.1 工程实践中的类似问题

1. 数据包重组：

   • 网络传输中数据包可能乱序到达
   • 需要按序号重组原始数据

2. 文件分块存储：

   • 大文件分块存储在不同位置
   • 需要验证所有块是否完整且顺序正确

3. 事务操作验证：

   • 数据库操作日志的连续性检查
   • 验证日志序列是否完整

10.2 个人解题心得

在实际解决这个问题时，有几点关键体会：

1. 问题简化：最初可能会考虑复杂的全排列搜索，但通过分析发现只需要关注首元素匹配就能大大简化问题。

2. 测试驱动：先编写测试用例再实现代码，可以更快发现逻辑漏洞，特别是边界条件。

3. 性能直觉：对于数组操作问题，哈希表+线性扫描的组合往往能提供最优的O(n)解决方案。

4. 代码简洁性：保持代码简洁明了比过早优化更重要，清晰的逻辑更容易调试和维护。

10.3 后续学习建议

要进一步提升这类问题的解决能力，建议：

1. 系统学习哈希技术：深入理解各种哈希表实现及其适用场景。

2. 掌握双指针技巧：这是解决数组/字符串问题的强大工具。

3. 练习更多变种问题：尝试解决允许重复元素或部分匹配的变种问题。

4. 分析优秀解法：在leetcode讨论区学习其他选手的高效解法，比较不同思路的优劣。