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

难度: Medium

给你一个长度为 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⁷

Submission

运行时间: 32 ms

内存: 16.2 MB

class Solution:
    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:
        k = 0
        for g in groups:
            while k + len(g) <= len(nums):
                if nums[k:k+len(g)] == g:
                    k+= len(g)
                    break
                k+=1
            else:
                return False
        return True

Explain

这个题解采用的是从左到右遍历 `nums` 数组的方法来寻找每个 `groups[i]` 的匹配项。其主要思路是使用一个指针 `k` 来标记 `nums` 中当前搜索的起始位置。对于 `groups` 中的每一个子数组 `g`，通过循环判断 `nums` 的一个子串（从 `k` 开始，长度与 `g` 相同）是否与 `g` 完全匹配。如果匹配，则将 `k` 移动到该匹配子串的末尾，继续寻找下一个 `groups` 中的子数组。如果当前位置的子串不匹配，`k` 则向右移动一个位置，继续尝试匹配。如果 `nums` 中的位置不足以容纳当前的 `g`，则返回 `false`。如果所有的 `groups` 元素都能在 `nums` 中按顺序找到匹配的不相交子数组，则返回 `true`。

时间复杂度: O(sum(len(groups[i])) * len(nums))

空间复杂度: O(1)

class Solution:
    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:
        k = 0  # 初始化 nums 的起始搜索位置
        for g in groups:  # 遍历每一个 group
            while k + len(g) <= len(nums):  # 确保 nums 有足够的剩余空间来匹配当前 group
                if nums[k:k+len(g)] == g:  # 检查从 k 开始的子数组是否与 g 匹配
                    k += len(g)  # 如果匹配，移动 k 到匹配子数组之后
                    break  # 退出当前循环，处理下一个 group
                k += 1  # 如果不匹配，k 向右移动一位
            else:  # 如果内部 while 循环正常结束而没有 break，则表示未找到匹配的子数组
                return False
        return True  # 所有 groups 都成功匹配

Explore

在这种情况下，可以优化算法通过先检查nums剩余长度是否小于当前group的长度。如果是，那么可以直接跳过后续的比较并返回false，因为不可能有足够的空间来匹配这个group。这样可以减少不必要的比较，提高算法效率。

这种情况发生在当nums数组中无法找到与当前group匹配的子数组时。例如，如果nums是[1, 2, 3, 4]，而当前的group是[5, 6]，while循环会尝试在nums中找到与[5, 6]匹配的子数组。当k移动到数组结束时，如果没有找到匹配的子数组，则while循环正常结束，没有执行break，此时应返回false，表示group无法在nums中按顺序匹配。

将指针k移动到匹配子数组之后可以避免重复和不必要的匹配。因为题目要求的是寻找不相交的子数组，一旦一个group在nums中找到了匹配，接下来应该寻找的是下一个group。从匹配子数组的末尾开始搜索下一个group可以确保不会有交叉覆盖，从而满足题目的要求。这样做提高了算法的执行效率和逻辑清晰度。

当前算法的确是简单的线性搜索，效率较低，特别是在nums和group较长的情况下。采用更高效的字符串匹配算法，如KMP算法，可以显著提高搜索效率。KMP算法通过预处理pattern（在本题中即为group）来避免不必要的比较，能够在O(n)时间内完成搜索，这比简单的线性搜索要高效得多。