力扣每日一题2022-09-22简单题：能否连接形成数组

---

题目描述

能否连接形成数组

---

思路

哈希表

因为arr每个整数互不相同，且pieces的整数也互不相同，所以可以通过arr固定pieces的位置，使用哈希表记录pieces各个数组的首元素与数组下标的对应关系。
不断将pieces中的数组与数组arr相对应，对于当前遍历的元素arr[i]，如果不存在哈希表中，说明无法将pieces与数组arr相对应，直接返回false；否则我们找到对应的数组pieces[j]，然后将它与arr[i]及之后的整数进行比较，比较过程中，如果判断相等不成立，则返回false，判断都相等后，将i相应地向后移。全部pieces都匹配成功后，返回true。

Python实现

class Solution:
    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:
        index = {p[0] : i for i, p in enumerate(pieces)}
        i = 0
        while i < len(arr):
            if arr[i] not in index:
                return False
            p = pieces[index[arr[i]]]
            if arr[i: i+len(p)] != p:
                return False
            i += len(p)
        return True
1
2
3
4
5
6
7
8
9
10
11
12

Java实现

class Solution {
    public boolean canFormArray(int[] arr, int[][] pieces) {
        int n = arr.length, m = pieces.length;
        Map<Integer, Integer> index = new HashMap<>();
        for (int i = 0; i < m; i++) {
            index.put(pieces[i][0], i);
        }
        for (int i = 0; i < n;) {
            if (!index.containsKey(arr[i])) return false;
            int j = index.get(arr[i]);
            int len = pieces[j].length;
            for (int k = 0; k < len; k++) {
                if (arr[i+k] != pieces[j][k]) {
                    return false;
                }
            }
            i += len;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

C++实现

class Solution {
public:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
        unordered_map<int, int> index;
        for (int i = 0; i < pieces.size(); i++) {
            index[pieces[i][0]] = i;
        }
        for (int i = 0; i < arr.size();) {
            auto it = index.find(arr[i]);
            if (it == index.end()) {
                return false;
            }
            for (int x : pieces[it->second]) {
                if (arr[i++] != x) {
                    return false;
                }
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21