form-array-by-concatenating-subarrays-of-another-array

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a 2D integer array <code>groups</code> of length <code>n</code>. You are also given an integer array <code>nums</code>.

You are asked if you can choose <code>n</code> disjoint subarrays from the array <code>nums</code> such that the <code>ith</code> subarray is equal to <code>groups[i]</code> (0-indexed), and if <code>i &gt; 0</code>, the <code>(i-1)th</code> subarray appears before the <code>ith</code> subarray in <code>nums</code> (i.e. the subarrays must be in the same order as <code>groups</code>).

Return <code>true</code> if you can do this task, and <code>false</code> otherwise.

Note that the subarrays are disjoint if and only if there is no index <code>k</code> such that <code>nums[k]</code> belongs to more than one subarray. A subarray is a contiguous sequence of elements within an array.

&nbsp;
Example 1:

<pre>
Input: groups = [[1,-1,-1],[3,-2,0]], nums = [1,-1,0,1,-1,-1,3,-2,0]
Output: true
Explanation: You can choose the 0th subarray as [1,-1,0,1,-1,-1,3,-2,0] and the 1st one as [1,-1,0,1,-1,-1,3,-2,0].
These subarrays are disjoint as they share no common nums[k] element.
</pre>

Example 2:

<pre>
Input: groups = [[10,-2],[1,2,3,4]], nums = [1,2,3,4,10,-2]
Output: false
Explanation: Note that choosing the subarrays [1,2,3,4,10,-2] and [1,2,3,4,10,-2] is incorrect because they are not in the same order as in groups.
[10,-2] must come before [1,2,3,4].
</pre>

Example 3:

<pre>
Input: groups = [[1,2,3],[3,4]], nums = [7,7,1,2,3,4,7,7]
Output: false
Explanation: Note that choosing the subarrays [7,7,1,2,3,4,7,7] and [7,7,1,2,3,4,7,7] is invalid because they are not disjoint.
They share a common elements nums[4] (0-indexed).
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>groups.length == n</code></li>
	<li><code>1 &lt;= n &lt;= 103</code></li>
	<li><code>1 &lt;= groups[i].length, sum(groups[i].length) &lt;= 103</code></li>
	<li><code>1 &lt;= nums.length &lt;= 103</code></li>
	<li><code>-107 &lt;= groups[i][j], nums[k] &lt;= 107</code></li>
</ul>

canChoose

Form Array by Concatenating Subarrays of Another Array

Greedy

Array

Two Pointers

String Matching

给你一个长度为 <code>n</code> 的二维整数数组 <code>groups</code> ，同时给你一个整数数组 <code>nums</code> 。

你是否可以从 <code>nums</code> 中选出 <code>n</code> 个 不相交 的子数组，使得第 <code>i</code> 个子数组与 <code>groups[i]</code> （下标从 0 开始）完全相同，且如果 <code>i > 0</code> ，那么第 <code>(i-1)</code> 个子数组在 <code>nums</code> 中出现的位置在第 <code>i</code> 个子数组前面。（也就是说，这些子数组在 <code>nums</code> 中出现的顺序需要与 <code>groups</code> 顺序相同）

如果你可以找出这样的 <code>n</code> 个子数组，请你返回 <code>true</code> ，否则返回 <code>false</code> 。

如果不存在下标为 <code>k</code> 的元素 <code>nums[k]</code> 属于不止一个子数组，就称这些子数组是 不相交 的。子数组指的是原数组中连续元素组成的一个序列。

 

示例 1：

<pre>
输入：groups = [[1,-1,-1],[3,-2,0]], nums = [1,-1,0,1,-1,-1,3,-2,0]
输出：true
解释：你可以分别在 nums 中选出第 0 个子数组 [1,-1,0,1,-1,-1,3,-2,0] 和第 1 个子数组 [1,-1,0,1,-1,-1,3,-2,0] 。
这两个子数组是不相交的，因为它们没有任何共同的元素。
</pre>

示例 2：

<pre>
输入：groups = [[10,-2],[1,2,3,4]], nums = [1,2,3,4,10,-2]
输出：false
解释：选择子数组 [1,2,3,4,10,-2] 和 [1,2,3,4,10,-2] 是不正确的，因为它们出现的顺序与 groups 中顺序不同。
[10,-2] 必须出现在 [1,2,3,4] 之前。
</pre>

示例 3：

<pre>
输入：groups = [[1,2,3],[3,4]], nums = [7,7,1,2,3,4,7,7]
输出：false
解释：选择子数组 [7,7,1,2,3,4,7,7] 和 [7,7,1,2,3,4,7,7] 是不正确的，因为它们不是不相交子数组。
它们有一个共同的元素 nums[4] （下标从 0 开始）。
</pre>

 

提示：

<ul>
	<li><code>groups.length == n</code></li>
	<li><code>1 <= n <= 103</code></li>
	<li><code>1 <= groups[i].length, sum(groups[i].length) <= 103</code></li>
	<li><code>1 <= nums.length <= 103</code></li>
	<li><code>-107 <= groups[i][j], nums[k] <= 107</code></li>
</ul>