This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 1764 on LeetCode. Get an array by concatenating a subarray of another array with moderate difficulty.

Tag: double pointer

You are given a two dimensional integer array groups of length n and an integer array nums.

Can you select n disjoint subarrays from nums such that the i-th subarray is exactly the same as groups[I] (subindexes start at 0), and if I > 0, the (i-1) subarray appears before the i-th subarray in NUMs? (That is, these subarrays need to appear in numS in the same order as the groups order)

Return true if you can find n such subarrays, false otherwise.

If no element nums[k] with subscript K belongs to more than one subarray, these subarrays are said to be disjoint. A subarray is a sequence of contiguous elements in the original array.

Example 1:

Input: groups = [[1, 1, 1], [3, 2, 0]], nums = [1, 1, 1, 1, 1, 3, 2, 0] output: true interpretation: You can select 0 is the array in the nums respectively [1, 1, 1, 1, 1, 3, 2, 0) and 1 is the array [1, 1, 1, 1, 1, 3, 2, 0). The two subarrays are disjoint because they don't have any elements in common.Copy the code

Example 2:

Input: groups = [[10, 2], [1, 2, 3, 4]], nums = [,2,3,4,10, 1-2] output: false interpretation: It is incorrect to select the subarrays [1,2,3,4,10,-2] and [1,2,3,4,10,-2] because they appear in a different order than in groups. [10,-2] must come before [1,2,3,4].Copy the code

Example 3:

Input: groups = [[1, 2, 3], [3, 4]], nums =,7,1,2,3,4,7,7 [7] output: false interpretation: It is incorrect to select subarrays [7,7,1,2,3,4,7,7] and [7,7,1,2,3,4,7,7] because they are not inintersecting subarrays. They have a common element, nums[4] (subscripts start at 0).Copy the code

Tip:

  • groups.length == n
  • 1 <= n <=
    1 0 3 10^3
  • 1 <= groups[i].length, sum(groups[i].length) <=
    1 0 3 10^3
  • 1 <= nums.length <=
    1 0 3 10^3
  • –
    1 0 7 10^7     <= groups[i][j], nums[k] <=
    1 0 7 10^7

Simple solution

It’s essentially a simulation.

Use the I pointer to represent the location to which NUMS is currently enumerated; J stands for which array to enumerate in groups.

CNT represents the number of matched arrays.

  • wheniThe beginning of a continuous sumgroups[j]Match:jMove the pointer one bit to the right (to match the next array),iThe pointer moves to the rightgroups[j].lengthLength.
  • wheniThe beginning of a continuous sumgroups[j]Don’t match:iMove one to the right.

Code:

class Solution {
    public boolean canChoose(int[][] gs, int[] nums) {
        int n = nums.length, m = gs.length;
        int cnt = 0;
        for (int i = 0, j = 0; i < n && j < m;) {
            if (check(gs[j], nums, i)) {
                i += gs[j++].length;
                cnt++;
            } else{ i++; }}return cnt == m;
    }
    boolean check(int[] g, int[] nums, int i) {
        int j = 0;
        for(; j < g.length && i < nums.length; j++, i++) {if(g[j] ! = nums[i])return false;
        }
        returnj == g.length; }}Copy the code
  • Time complexity: O(n∗m)O(n * m)O(n∗m)
  • Space complexity: O(1)O(1)O(1)

The last

This is the No.1764 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.