1764. 通过毗连另一个数组的子数组得到一个数组(难度:中等)

手机游戏开发者 2024-10-8 18:57:37 33 0 来自 中国
题目链接:https://leetcode.cn/problems/form-array-by-concatenating-subarrays-of-another-array/
题目形貌:

给你一个长度为 n 的二维整数数组 groups ,同时给你一个整数数组 nums 。
你是否可以从 nums 中选出 n 个 不相交 的子数组,使得第 i 个子数组与 groups (下标从 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 == n
  • 1 <= n <= 103
  • 1 <= groups.length, sum(groups.length) <= 103
  • 1 <= nums.length <= 103
  • -107 <= groups[j], nums[k] <= 107
解法:暴力法

直接遍历groups数组中的每一个数组元素groups,利用index来标识当前遍历nums的下标,在遍历对照groups数组之前,都先用temp来把当前满足groups[i-1]的最小下标index缓存起来。每一个在nums查找有没有一连的一段子数组与groups是雷同的,若中心有一个元素不满足,则让index = temp + 1,继承重新遍历groups,若遍历完nums也没有完全匹配groups,则返回false,否则返回true。
代码:
您需要登录后才可以回帖 登录 | 立即注册

Powered by CangBaoKu v1.0 小黑屋藏宝库It社区( 冀ICP备14008649号 )

GMT+8, 2024-10-18 16:47, Processed in 0.119467 second(s), 33 queries.© 2003-2025 cbk Team.

快速回复 返回顶部 返回列表