5分钟
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：
输入：groups = [[1,-1,-1],[3,-2,0]], nums = [1,-1,0,1,-1,-1,3,-2,0]
输出：true
解释：你可以分别在 nums 中选出第 0 个子数组 [1,-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] 是不正确的，因为它们出现的顺序与 groups 中顺序不同。[10,-2] 必须出现在 [1,2,3,4] 之前。
示例 3：
输入：groups = [[1,2,3],[3,4]], nums = [7,7,1,2,3,4,7,7]
输出：false
解释：选择子数组 [1,2,3] 和 [3,4,] 是不正确的，因为它们不是不相交子数组。它们有一个共同的元素 nums[4] （下标从 0 开始）。
提示：
groups.length == n
1 <= n <= 103
1 <= groups[i].length, sum(groups[i].length) <= 103
1 <= nums.length <= 103
-107 <= groups[i][j], nums[k] <= 107
思路
定义双指针i和j，分别指向groups[i]和nums[j]，同时注意双指针不可超出其指向的数组边界。 在i和j循环的过程中，有k指针指向groups[i]中第k个元素groups[i][k]，如果nums[j+k]和groups[i][k]不相等，则i原地停留，j往后递进，直到找到和groups[i][k]相等的元素为止。
同时需要注意边界：由于要生成n个不相交的子数组，即保证每一组groups[i]都是子数组，对于j指针而言，如果j+groups[i].length超出了nums[j]的边界，则说明groups[i]以及之后的数组都无法作为nums[j]的子数组。
若groups[i]可以作为子数组，则i往后递进，同时为了确保每一个groups[i]不相交，j要越过当前已匹配的元素，即往后移动的长度为groups[i].length。
思路递推
以实例一：groups = [[1,-1,-1],[3,-2,0]], nums = [1,-1,0,1,-1,-1,3,-2,0]为例
- 初始状态，i = 0,j = 0，nums.length = 9
- groups[i] = [1,-1,-1]，nums[j] = 1
- j(0)+group[i].length(3) <= nums.length(9)，遍历继续
- 遍历groups[i]，发现groups[i][2] = -1,nums[j+2] = nums[2] = 0，二者不相等，j往后递进+1.
- i = 0,j = 1
- groups[i] = [1,-1,-1]，nums[j] = -1
- j(1)+group[i].length(3) < nums.length(9)，遍历继续
- 遍历groups[i]，发现groups[i][0] = 1,nums[j+0] = nums[1] = -1，二者不相等，j往后递进+1.
- i = 0,j = 2
- groups[i] = [1,-1,-1]，nums[j] = 0
- j(2)+group[i].length(3) < nums.length(9)，遍历继续
- 遍历groups[i]，发现groups[i][0] = 1,nums[j+0] = nums[2] = 0，二者不相等，j往后递进+1.
- i = 0,j = 3
- groups[i] = [1,-1,-1]，nums[j] = 1
- j(3)+group[i].length(3) < nums.length(9)，遍历继续
- 遍历groups[i]，发现:
- groups[i][0] = nums[j+0] = nums[3] = 1
- groups[i][1] = nums[j+1] = nums[4] = -1
- groups[i][2] = nums[j+2] = nums[5] = -1
- 因此，groups[i]可以作为nums的一个不相交子序列，i往后递进+1，同时为了保证子数组不相交，j往后递进groups[i].length的长度
- i = 1,j = 6
- groups[i] = [3，-2,0]，nums[j] = 3
- j(6)+group[i].length(3) <= nums.length(9)，遍历继续
- 遍历groups[i]，发现:
- groups[i][0] = nums[j+0] = nums[6] = 3
- groups[i][1] = nums[j+1] = nums[7] = -2
- groups[i][2] = nums[j+2] = nums[8] = 0
- 因此，groups[i]可以作为nums的一个不相交子序列，i往后递进+1，同时为了保证子数组不相交，j往后递进groups[i].length的长度
- i = 3，j = 9，二者达到各自的数组边界，结束循环
- 判断i是否和groups.length相等，只有i到达groups末尾，才能证明groups[0]…groups[i-1]均可以构成不相交子数组。
代码实现
public static boolean canChoose(int[][] groups, int[] nums) {
int groupLength = groups.length,numLength = nums.length;
// 双指针，分别指向groups[i]和nums[j]
int i = 0,j = 0;
while (i < groupLength && j < numLength){
// 判断当前groups[i]是否为nums的连续子序列
int currentLength = groups[i].length;
if (j + currentLength > numLength)
// 如果当前j加上group[i]的长度若超过nums的总长度，则说明无法生成groupLength个连续子数组
return false;
boolean isSub = true;
for (int k = 0; k < currentLength; k++) {
if (groups[i][k] != nums[j+k]){
// 如果当前group[i]的第k个元素和nums[j+k]的元素不相等，则让j指针往后移动，直到匹配到相等的元素为止
isSub = false;
break;
}
}
if (isSub){
// group[i]已完成匹配，转向下一个group子数组
i++;
// 为了保证不相交，j往后递进group[i]的长度，跳过nums中已匹配的元素
j += currentLength;
} else {
// 说明当前groups[i]不匹配，i原地停留，j指针往后移动，直到匹配到和group[i]中元素相等的元素为止
j++;
}
}
// 如果i指向groups末尾，则说明所有的groups[i]均能成为nums的不相交的子数组
return i == groupLength;
}
public static void test(){
System.out.println(canChoose(new int[][]{{1,-1,-1},{3,-2,0}},new int[]{1,-1,0,1,-1,-1,3,-2,0}));
System.out.println(canChoose(new int[][]{{10,-2},{1,2,3,4}},new int[]{1,2,3,4,10,-2}));
}