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

题目描述

这是 LeetCode 上的 1764. 通过连接另一个数组的子数组得到一个数组 ，难度为 中等。

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

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

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

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

示例 1：

1
2
3
4
5
6
输入：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：
1
2
3
4
5
6
输入：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：
1
2
3
4
5
6
输入：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^3$
  • $1 <= groups[i].length, sum(groups[i].length) <= 10^3$
  • $1 <= nums.length <= 10^3$
  • $-10^7 <= groups[i][j], nums[k] <= 10^7$

双指针

为了方便，将 groups 记为 gs。

从前往后处理每个 $gs[i]$，使用 idx 记录当前使用到 nums 中的哪一位（即 $[0, … (idx - 1)]$ 的 $nums[i]$ 已经用于匹配 $gs[0, … (i - 1)]$。

每次尝试从 idx 出发匹配 gs[i]，若能匹配成功，则整段更新 $idx = idx + gs[i].length$；否则将 idx 后移一位，继续尝试匹配 gs[i]。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean canChoose(int[][] gs, int[] nums) {
        int m = nums.length, idx = 0;
        out:for (int[] info : gs) {
            for (int j = idx; j + info.length <= m; j++) {
                boolean ok = true;
                for (int k = 0; k < info.length && ok; k++) {
                    if (nums[j + k] != info[k]) ok = false;
                }
                if (ok) {
                    idx = j + info.length;
                    continue out;
                }
            }
            return false;
        }
        return true;
    }
}

C++ 代码（用 ct 模拟 continue tag 效果）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool canChoose(vector<vector<int>>& gs, vector<int>& nums) {
        int m = nums.size(), idx = 0;
        out:for (auto& info : gs) {
            bool ct = false;
            for (int j = idx; j + info.size() <= m; j++) {
                bool ok = true;
                for (int k = 0; k < info.size() && ok; k++) {
                    if (nums[j + k] != info[k]) ok = false;
                }
                if (ok) {
                    idx = j + info.size();
                    ct = true;
                    break;
                }
            }
            if (!ct) return false;
        }
        return true;
    }
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def canChoose(self, gs: List[List[int]], nums: List[int]) -> bool:
        m, idx = len(nums), 0
        for info in gs:
            for j in range(idx, len(nums) - len(info) + 1):
                if all(nums[j + k] == info[k] for k in range(len(info))):
                    idx = j + len(info)
                    break
            else:
                return False
        return True

TypeScript 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function canChoose(gs: number[][], nums: number[]): boolean {
    let m = nums.length, idx = 0;
    for (const info of gs) {
        let ct = false;
        for (let j = idx; j + info.length <= m; j++) {
            let ok = true;
            for (let k = 0; k < info.length && ok; k++) {
                if (nums[j + k] !== info[k]) ok = false;
            }
            if (ok) {
                idx = j + info.length;
                ct = true;
                break;
            }
        }
        if (!ct) return false;
    }
    return true;
};

  • 时间复杂度：$O(n \times m)$
  • 空间复杂度：$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1764 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。