【2022-12-17每日一题】1764. 通过连接另一个数组的子数组得到一个数组[Medium]
2022-12-17
3分钟阅读时长
2022-12-17每日一题：1764. 通过连接另一个数组的子数组得到一个数组
难度：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 == n1 <= n <= 1031 <= groups[i].length, sum(groups[i].length) <= 1031 <= nums.length <= 103-107 <= groups[i][j], nums[k] <= 107
方法一：多层循环模拟过程（双指针）
自己
func canChoose(groups [][]int, nums []int) bool {
count, idx, n := 0, 0, len(nums)
for _, group := range groups {
IDX:
for ; idx < n; idx++ {
for i, x := range group {
// 越界直接返回false
if idx+i >= n {
return false
}
// 不匹配直接返回上上层
if x != nums[idx+i] {
continue IDX;
}
}
// 执行到这里说明已经匹配group
idx += len(group)
count++
break
}
}
return count == len(groups)
}
贪心枚举
// 写法1
func canChoose(groups [][]int, nums []int) bool {
m, n, i := len(nums), len(groups), 0
check := func (group, nums []int, j int) bool {
x, y, i := len(group), len(nums), 0
for ; i < x && j < y; i, j = i+1, j+1 {
if group[i] != nums[j] {
return false
}
}
return i == x
}
for j := 0; i < n && j < m; {
if check(groups[i], nums, j) {
j += len(groups[i])
i++
} else {
j++
}
}
return i == n
}
// 写法2
func canChoose(groups [][]int, nums []int) bool {
next:
for _, g := range groups {
for len(nums) >= len(g) {
if equal(nums[:len(g)], g) {
nums = nums[len(g):]
continue next
}
nums = nums[1:]
}
return false
}
return true
}
func equal(a, b []int) bool {
for i, x := range a {
if x != b[i] {
return false
}
}
return true
}
复杂度分析
- 时间复杂度：$O(mn)$。其中 m 是数组 nums 的长度，n是数组groups的长度。
- 空间复杂度：$O(1)$。
方法二：KMP 匹配算法
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
- 推荐题解
class Solution {
public boolean canChoose(int[][] groups, int[] nums) {
int k = 0;
for (int i = 0; i < groups.length; i++) {
k = find(nums, k, groups[i]);
if (k == -1) {
return false;
}
k += groups[i].length;
}
return true;
}
public int find(int[] nums, int k, int[] g) {
int m = g.length, n = nums.length;
if (k + g.length > nums.length) {
return -1;
}
int[] pi = new int[m];
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && g[i] != g[j]) {
j = pi[j - 1];
}
if (g[i] == g[j]) {
j++;
}
pi[i] = j;
}
for (int i = k, j = 0; i < n; i++) {
while (j > 0 && nums[i] != g[j]) {
j = pi[j - 1];
}
if (nums[i] == g[j]) {
j++;
}
if (j == m) {
return i - m + 1;
}
}
return -1;
}
}
时间复杂度：$O(m+∑gi)$，其中 m 是数组 nums 的长度，gi 是数组 groups[i] 的长度。最坏情况下，每一个 groups[i] 都调用一次 find，因此总时间复杂度为 O(m+∑gi)。
空间复杂度：O(maxgi)。对 groups[i] 调用一次 KMP 算法需要申请 O(gi) 的空间。