What is the main pattern to solve Form Array by Concatenating Subarrays of Another Array?

The main pattern is sequential two-pointer scanning with invariant tracking to match each group in order without overlap.

Can subarrays from groups overlap in nums?

No, the problem requires selecting disjoint subarrays; overlapping would violate the constraints and return false.

How do I handle a group that doesn't appear in nums?

If a group cannot be matched in the remaining suffix of nums, you should immediately return false as no valid selection exists.

Is there an optimized way to skip unnecessary comparisons?

Yes, by checking the first and last elements of a group against nums positions, you can skip positions that cannot possibly match, reducing scans.

What is the time complexity for this approach?

The worst-case time complexity is O(m * n), where m is the total length of all groups and n is the length of nums, as each element may be scanned multiple times.

#1764

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

通过连接另一个数组的子数组得到一个数组

给你一个长度为 n 的二维整数数组 groups ，同时给你一个整数数组 nums 。你是否可以从 nums 中选出 n 个不相交的子数组，使得第 i 个子数组与 groups[i] （下标从 0 开始）完全相同，且如果 i > 0 ，那么第 (i-1) 个子数组在 nums 中出现的位置在第…

数组双指针贪心字符串匹配

题目描述

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

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

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

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

示例 1：

输入：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] 。
这两个子数组是不相交的，因为它们没有任何共同的元素。

示例 2：

输入：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] 之前。

示例 3：

输入：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 开始）。

提示：

groups.length == n
1 <= n <= 10³
1 <= groups[i].length, sum(groups[i].length) <= 10³
1 <= nums.length <= 10³
-10⁷ <= groups[i][j], nums[k] <= 10⁷

lightbulb

解题思路

方法一：贪心枚举

我们贪心地枚举 nums 中每一个数 $nums[j]$ 作为子数组的开始，判断其是否与当前 $groups[i]$ 匹配，是则将指针 $i$ 往后移一位，将指针 $j$ 往后移动 $groups[i].length$ 位，否则将指针 $j$ 往后移动一位。

如果 $i$ 走到了 $groups.length$ ，说明所有的子数组都匹配上了，返回 true，否则返回 false。

时间复杂度 $O(n \times m)$ ，空间复杂度 $O(1)$ 。其中 $n$ 和 $m$ 分别为 groups 和 nums 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:
        n, m = len(groups), len(nums)
        i = j = 0
        while i < n and j < m:
            g = groups[i]
            if g == nums[j : j + len(g)]:
                j += len(g)
                i += 1
            else:
                j += 1
        return i == n

speed

复杂度分析

指标	值
时间	complexity is O(m * n) in the worst case, where m is the total length of all groups and n is the length of nums, since each element of nums may be scanned multiple times. Space complexity is O(1) extra space beyond input arrays, as matching is done in-place with pointers and no additional structures are required.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on maintaining the current nums pointer after each matched group to avoid overlapping.
question_mark
Expect you to explain why early termination is safe when a group cannot be matched in the remaining suffix.
question_mark
Look for clear handling of edge cases, like groups longer than remaining nums or repeated numbers.

warning

常见陷阱

外企场景

error
Assuming groups can overlap, which violates the disjoint requirement.
error
Restarting scan from the beginning of nums for each group instead of advancing the pointer.
error
Failing to check that each group fully matches a contiguous segment of nums, not just partially.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow groups to appear in any order and check if nums can form them in any sequence.
arrow_right_alt
Increase the constraints to larger arrays to test efficiency of two-pointer vs brute force.
arrow_right_alt
Require returning the starting indices of each matched group instead of a boolean.

help

常见问题

外企场景

继续练习

#1877 数组中最大数对和的最小值 #1537 最大得分 #2071 你可以安排的最多任务数目