重复子阵列的最大长度


难度级别 中等
经常问 的确 克拉 Roblox
排列 二进制搜索 动态编程 哈希

在问题“重复子数组的最大长度”中,我们给了两个数组Array 1和Array 2,您的任务是找到出现在两个子数组中的子数组的最大长度。 数组.

使用案列

输入:

[1,2,3,2,1]
[3,2,1,4,7]

输出:

3

说明:

因为子数组的最大长度是3,公共数组是[3,2,1]

重复子阵列的最大长度

算法

  1. 将输出设置为0。
  2. 声明一个可变整数数组,其长度比实际输入数组的长度大1。
  3. 从开始 数组的最后一个索引 检查array1 [i]是否等于array2 [j],如果为true,则val [i] [j] = val [i + 1] [j + 1] +1。
  4. 检查输出是否小于val [i] [j],然后执行output = val [i] [j]。
  5. 遍历整个数组并检查条件,我们获得最大输出。
  6. 返回输出。

说明

为了获得我们的输出,我们需要做一些简单的遍历。 为此,我们将输出初始化为0。然后我们将声明2-D 矩阵 长度比array1和array2的长度大一号。

我们将从数组的最后一个索引开始遍历两个数组。 因此,我们将检查一些条件并将结果存储在输出中。

因此,让我们以一个例子为例,并进一步进行。

使用案列

假设有一个数组为:

int array1 [] = {1,2,3,2,1};

int array2 [] = {3,2,1,4,7};

输出= 0;

  • i = 4,j = 4;

如果array1 [i] == array2 [j]返回false并且不做任何事情。

输出= 0;

  • i = 4,j = 3;

如果array1 [i] == array2 [j]返回false并且不做任何事情。

输出= 0;

  • i = 4,j = 2;

如果array1 [i] == array2 [j]返回true并且val [i] [j] = val [i + 1] [j + 1] +1

then val[4][2]=val[5][3]+1=1 then val[i][j]=1.

然后检查输出<val [i] [j]是否返回true并执行output = 1。

输出= 1;

  • i = 4,j = 1;

如果array1 [i] == array2 [j]返回false并且不做任何事情。

  • i = 4,j = 0;

如果array1 [i] == array2 [j]返回false并且不做任何事情。

  • i = 3,j = 4;

如果array1 [i] == array2 [j]返回false并且不做任何事情。

  • i = 3,j = 3;

如果array1 [i] == array2 [j]返回false并且不做任何事情。

  • i = 3,j = 2;

如果array1 [i] == array2 [j]返回false并且不做任何事情。

  • i = 3,j = 1;

如果array1 [i] == array2 [j]返回true并且val [i] [j] = val [i + 1] [j + 1] +1

然后val [3] [1] = val [4] [2] + 1 = 2然后val [3] [1] = 2。

然后检查输出<val [i] [j]是否返回true,并执行output = val [i] [j]。

输出= 2;

  • i = 3,j = 0;

如果array1 [i] == array2 [j]返回false并且不做任何事情。

  • i = 2,j = 4;

如果array1 [i] == array2 [j]返回false并且不做任何事情。

  • i = 2,j = 3;

如果array1 [i] == array2 [j]返回false并且不做任何事情。

  • i = 2,j = 2;

如果array1 [i] == array2 [j]返回false并且不做任何事情。

  • i = 2,j = 1;

如果array1 [i] == array2 [j]返回false并且不做任何事情。

  • i = 2,j = 0;

如果array1 [i] == array2 [j]返回true并且val [i] [j] = val [i + 1] [j + 1] +1

然后val [2] [0] = val [3] [1] + 1 = 2 +1然后val [2] [0] = 3。

然后检查输出<val [i] [j]是否返回true,并执行output = val [2] [0]。

输出= 3;

即使我们发现遍历中的元素相等,这也是重复数组的最大长度为3,但不会在输出中进行更新,因为这将不是子数组

假设在i = 1,j = 1处,我们将找到下一个类似的元素,因此它将执行val [1] [1] = val [2] [2] +1;

如果我们检查输出<val [1] [1],则每次返回false都不会执行任何操作。

因此,这里的输出为3。

实施

重复子数组最大长度的C ++程序

#include <iostream>
using namespace std;

int lengthOfRepeatedArray(int array1[], int array2[])
{
    int output = 0;
    int val[6][6]= {0};

    for (int i = 4; i >= 0; --i)
    {
        for (int j = 4; j >= 0; --j)
        {
            if (array1[i] == array2[j])
            {
                val[i][j] = val[i+1][j+1] + 1;
                if(output < val[i][j])
                {
                    output = val[i][j];
                }
            }
        }
    }
    return output;
}
int main()
{
    int a[]= {1,2,3,2,1};
    int b[]= {3,2,1,4,7};

    cout<<lengthOfRepeatedArray(a,b);
    return 0;
}
3

重复子数组最大长度的Java程序

class repeatedArrayLength
{
    public static int lengthOfRepeatedArray(int[] array1, int[] array2)
    {
        int output = 0;
        int val[][] = new int[array1.length + 1][array2.length + 1];
        for (int i = array1.length - 1; i >= 0; --i)
        {
            for (int j = array2.length - 1; j >= 0; --j)
            {
                if (array1[i] == array2[j])
                {
                    val[i][j] = val[i+1][j+1] + 1;
                    if(output < val[i][j])
                        output = val[i][j];
                }
            }
        }
        return output;
    }
    public static void main(String []args)
    {
        int a[]= {1,2,3,2,1};
        int b[]= {3,2,1,4,7};
        System.out.println(lengthOfRepeatedArray(a,b));
    }
}
3

重复子阵列最大长度的复杂度分析

时间复杂度

O(a×b) 哪里 “A” 是第一个数组的大小,并且 “ b” 是第二个数组的大小。

空间复杂度

O(a×b) 哪里 “A” 是第一个数组的大小,并且 “ b” 是第二个数组的大小。

参考