Medium

题目描述

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

请你判断是否能从数组 nums 中选择 n 个 不相交 的子数组，使得第 i 个子数组等于 groups[i] （下标从 0 开始），且如果 i > 0，那么第 (i-1) 个子数组在 nums 中出现在第 i 个子数组之前（即子数组必须按照与 groups 相同的顺序出现）。

如果你能完成这个任务，返回 true，否则返回 false。

注意，子数组是 不相交 的，当且仅当不存在下标 k 使得 nums[k] 属于多于一个子数组。子数组是数组中连续的元素序列。

示例 1：

输入：groups = [[1,-1,-1],[3,-2,0]], nums = [1,-1,0,1,-1,-1,3,-2,0]
输出：true
解释：你可以选择第 0 个子数组为 [1,-1,0,1,-1,-1,3,-2,0]，第 1 个子数组为 [1,-1,0,1,-1,-1,3,-2,0]。
这些子数组是不相交的，因为它们没有任何共同的 nums[k] 元素。

示例 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⁷

解题思路

这道题的核心思路是贪心匹配。我们需要按照 groups 的顺序，在 nums 中依次找到匹配的子数组。

解决思路如下：

  1. 贪心策略：对于每个 group，我们应该找到在 nums 中最早出现的匹配位置。这样可以为后续的 groups 留下最大的搜索空间。

  2. 双指针技术：维护一个指针 start 表示当前在 nums 中的搜索起始位置。对于每个 group，从 start 开始寻找匹配的子数组。

  3. 子数组匹配：对于当前 group，在 nums 中从 start 位置开始，逐一检查每个可能的起始位置是否能完全匹配当前 group。

  4. 更新搜索位置：一旦找到匹配的子数组，更新 start 为该子数组结束位置的下一个位置，确保子数组不相交。

具体实现中，我们可以编写一个辅助函数来检查从指定位置开始的子数组是否与目标 group 匹配。时间复杂度为 O(n × m)，其中 n 是 nums 的长度，m 是所有 groups 的总长度。

推荐解法：使用贪心 + 双指针的方法，代码简洁且效率较高。

代码实现

class Solution {
public:
    bool canChoose(vector<vector<int>>& groups, vector<int>& nums) {
        int start = 0;
        
        for (auto& group : groups) {
            bool found = false;
            
            // 在nums中从start位置开始寻找匹配group的子数组
            for (int i = start; i <= (int)nums.size() - (int)group.size(); i++) {
                if (isMatch(nums, i, group)) {
                    start = i + group.size();
                    found = true;
                    break;
                }
            }
            
            if (!found) return false;
        }
        
        return true;
    }
    
private:
    bool isMatch(vector<int>& nums, int start, vector<int>& group) {
        for (int i = 0; i < group.size(); i++) {
            if (nums[start + i] != group[i]) {
                return false;
            }
        }
        return true;
    }
};

class Solution:
    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:
        start = 0
        
        for group in groups:
            found = False
            
            # 在nums中从start位置开始寻找匹配group的子数组
            for i in range(start, len(nums) - len(group) + 1):
                if self.is_match(nums, i, group):
                    start = i + len(group)
                    found = True
                    break
            
            if not found:
                return False
        
        return True
    
    def is_match(self, nums: List[int], start: int, group: List[int]) -> bool:
        for i in range(len(group)):
            if nums[start + i] != group[i]:
                return False
        return True

public class Solution {
    public bool CanChoose(int[][] groups, int[] nums) {
        int start = 0;
        
        foreach (var group in groups) {
            bool found = false;
            
            // 在nums中从start位置开始寻找匹配group的子数组
            for (int i = start; i <= nums.Length - group.Length; i++) {
                if (IsMatch(nums, i, group)) {
                    start = i + group.Length;
                    found = true;
                    break;
                }
            }
            
            if (!found) return false;
        }
        
        return true;
    }
    
    private bool IsMatch(int[] nums, int start, int[] group) {
        for (int i = 0; i < group.Length; i++) {
            if (nums[start + i] != group[i]) {
                return false;
            }
        }
        return true;
    }
}

var canChoose = function(groups, nums) {
    let start = 0;
    
    for (let group of groups) {
        let found = false;
        
        // 在nums中从start位置开始寻找匹配group的子数组
        for (let i = start; i <= nums.length - group.length; i++) {
            if (isMatch(nums, i, group)) {
                start = i + group.length;
                found = true;
                break;
            }
        }
        
        if (!found) return false;
    }
    
    return true;
    
    function isMatch(nums, start, group) {
        for (let i = 0; i < group.length; i++) {
            if (nums[start + i] !== group[i]) {
                return false;
            }
        }
        return true;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × m)，其中 n 是 nums 数组的长度，m 是所有 groups 的总长度。在最坏情况下，需要遍历 nums 中的每个位置来寻找匹配
空间复杂度O(1)，只使用了常数级别的额外空间，不包括输入数组