1764. Form Array by Concatenating Subarrays of Another Array
Medium
You are given a 2D integer array
groups
of length n
. You are also given an integer array nums
.You are asked if you can choose
n
disjoint subarrays from the array nums
such that the ith
subarray is equal to groups[i]
(0-indexed), and if i > 0
, the (i-1)th
subarray appears before the ith
subarray in nums
(i.e. the subarrays must be in the same order as groups
).Return
true
if you can do this task, and false
otherwise.Note that the subarrays are disjoint if and only if there is no index
k
such that nums[k]
belongs to more than one subarray. A subarray is a contiguous sequence of elements within an array.Example 1:
Input: groups = [[1,-1,-1],[3,-2,0]], nums = [1,-1,0,1,-1,-1,3,-2,0]
Output: true
Explanation: You can choose the 0th subarray as [1,-1,0,1,-1,-1,3,-2,0] and the 1st one as [1,-1,0,1,-1,-1,3,-2,0].
These subarrays are disjoint as they share no common nums[k] element.
Example 2:
Input: groups = [[10,-2],[1,2,3,4]], nums = [1,2,3,4,10,-2]
Output: false
Explanation: Note that choosing the subarrays [1,2,3,4,10,-2] and [1,2,3,4,10,-2] is incorrect because they are not in the same order as in groups.
[10,-2] must come before [1,2,3,4].
Example 3:
Input: groups = [[1,2,3],[3,4]], nums = [7,7,1,2,3,4,7,7]
Output: false
Explanation: Note that choosing the subarrays [7,7,1,2,3,4,7,7] and [7,7,1,2,3,4,7,7] is invalid because they are not disjoint.
They share a common elements nums[4] (0-indexed).
Constraints:
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
func canChoose(groups [][]int, nums []int) bool {
index := 0
for _, group := range groups {
flag := false
for i := index; i <= len(nums) - len(group) ; i++ {
if check(group, nums[i:i+len(group)]) { // 比對陣列,比對相同了將 index 改成陣列後一個數字
index = i + len(group)
flag = true
break
}
}
if !flag { return false }
}
return true
}
func check(group []int, nums []int) bool { // 比對兩個整數陣列是否相同
if len(group) != len(nums) {
return false
}
for i:=0; i<len(group); i++ {
if group[i] != nums[i] {
return false
}
}
return true
}
Last modified 4mo ago