Easy

题目描述

给你一个由不同整数组成的数组 arr 和一个整数数组的数组 pieces，其中 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 <= 100
  • sum(pieces[i].length) == arr.length
  • 1 <= pieces[i].length <= arr.length
  • 1 <= arr[i], pieces[i][j] <= 100
  • arr 中的整数是不同的
  • pieces 中的整数是不同的（即，如果我们将 pieces 展开为一维数组，该数组中的所有整数都是不同的）

解题思路

这道题的核心思路是验证能否通过拼接 pieces 中的子数组来重构原数组 arr。

思路分析：

我们可以使用哈希表来建立映射关系。关键观察是：每个 piece 的第一个元素是该 piece 的唯一标识，因为所有数字都是不同的。

解法一（推荐）：哈希表映射法

  1. 用哈希表存储每个 piece 的第一个元素到整个 piece 的映射
  2. 遍历 arr，对于每个位置：
    • 如果当前元素是某个 piece 的起始元素，找到对应的 piece
    • 验证从当前位置开始的子序列是否与该 piece 完全匹配
    • 如果匹配，跳过整个 piece 的长度；如果不匹配，返回 false

解法二：直接匹配法 对于 arr 中的每个位置，尝试在 pieces 中找到以当前元素开始的 piece，然后验证是否完全匹配。

时间复杂度上两种解法相似，但哈希表法在查找 piece 时更高效。

代码实现

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

class Solution:
    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:
        piece_map = {piece[0]: piece for piece in pieces}
        
        i = 0
        while i < len(arr):
            if arr[i] not in piece_map:
                return False
            
            piece = piece_map[arr[i]]
            for j in range(len(piece)):
                if i >= len(arr) or arr[i] != piece[j]:
                    return False
                i += 1
        
        return True

public class Solution {
    public bool CanFormArray(int[] arr, int[][] pieces) {
        var pieceMap = new Dictionary<int, int[]>();
        foreach (var piece in pieces) {
            pieceMap[piece[0]] = piece;
        }
        
        int i = 0;
        while (i < arr.Length) {
            if (!pieceMap.ContainsKey(arr[i])) {
                return false;
            }
            
            var piece = pieceMap[arr[i]];
            for (int j = 0; j < piece.Length; j++) {
                if (i >= arr.Length || arr[i] != piece[j]) {
                    return false;
                }
                i++;
            }
        }
        
        return true;
    }
}

var canFormArray = function(arr, pieces) {
    const pieceMap = new Map();
    for (const piece of pieces) {
        pieceMap.set(piece[0], piece);
    }
    
    let i = 0;
    while (i < arr.length) {
        if (!pieceMap.has(arr[i])) {
            return false;
        }
        
        const piece = pieceMap.get(arr[i]);
        for (let j = 0; j < piece.length; j++) {
            if (i >= arr.length || arr[i] !== piece[j]) {
                return false;
            }
            i++;
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(m)

其中 n 是数组 arr 的长度，m 是 pieces 数组的长度。时间复杂度为 O(n) 因为我们只需要遍历 arr 一次，空间复杂度为 O(m) 用于存储哈希表。