1640 能否连接形成数组

本文最后更新于：2022年9月22日 晚上

给你一个整数数组 arr ，数组中的每个整数 互不相同 。另有一个由整数数组构成的数组 pieces，其中的整数也 互不相同 。请你以 任意顺序 连接 pieces 中的数组以形成 arr 。但是，不允许 对每个数组 pieces[i] 中的整数重新排序。

如果可以连接 pieces 中的数组形成 arr ，返回 true ；否则，返回 false 。

示例 1：

1
2
3
输入：arr = [15,88], pieces = [[88],[15]]
输出：true
解释：依次连接 [15] 和 [88]

示例 2：

1
2
3
输入：arr = [49,18,16], pieces = [[16,18,49]]
输出：false
解释：即便数字相符，也不能重新排列 pieces[0]

示例 3：

1
2
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 扁平化成一维数组，数组中的所有整数互不相同）

Solution

参考@LeetCode官方

  • 哈希

使用哈希表 index 记录 pieces 各个数组的首元素与数组下标的对应关系。

不断地将 pieces 中的数组与数组 arr 相对应，对于当前遍历的元素 arr[i]，如果它不存在于哈希表中，说明我们无法将 pieces 与数组 arr 相对应，直接返回 false；否则我们找到对应的数组 pieces[j]，然后将它与 arr[i] 及之后的整数进行比较（在比较过程中，如果判断相等不成立，直接返回 false），判断都相等后，将 i 相应地向后移。全部 pieces 都匹配成功后，返回 true。

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