文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個整數(shù)數(shù)組 arr ，數(shù)組中的每個整數(shù) 互不相同 。
另有一個由整數(shù)數(shù)組構(gòu)成的數(shù)組 pieces，其中的整數(shù)也 互不相同 。請你以 任意順序 連接 pieces 中的數(shù)組以形成 arr 。但是，不允許 對每個數(shù)組 pieces[i] 中的整數(shù)重新排序。

如果可以連接 pieces 中的數(shù)組形成 arr ，返回 true ；否則，返回 false 。

示例 1： 輸入：arr = [85], pieces = [[85]] 輸出：true示例 2： 輸入：arr = [15,88], pieces = [[88],[15]] 輸出：true 解釋：依次連接 [15] 和 [88]示例 3： 輸入：arr = [49,18,16], pieces = [[16,18,49]] 輸出：false 解釋：即便數(shù)字相符，也不能重新排列 pieces[0]示例 4： 輸入：arr = [91,4,64,78], pieces = [[78],[4,64],[91]] 輸出：true 解釋：依次連接 [91]、[4,64] 和 [78]示例 5： 輸入：arr = [1,3,5,7], pieces = [[2,4,6,8]] 輸出：false提示： 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 中的整數(shù) 互不相同 pieces 中的整數(shù) 互不相同（也就是說，如果將 pieces 扁平化成一維數(shù)組，數(shù)組中的所有整數(shù)互不相同）

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/check-array-formation-through-concatenation
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 把 pieces[i] 中的第一個數(shù)作為 key，pieces[i] 作為 value，存入哈希map，后面可以快速查找
• 遍歷 arr 數(shù)組，查找當(dāng)前數(shù)字是否在哈希map中，不在，false
• 在的話，遍歷 value 和 arr，看是否一致

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

0 ms 10.3 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1640. 能否连接形成数组（哈希）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。