给定一个整数数组，找到最大子数组的长度，使得至少 1 个数字（来自前 k 个数字）不存在于其中

Question

问题：给定一个整数数组，整数范围从 1 到 k。不必所有 k 个整数都存在。例如。k = 3 and Array = [1,2,1,1,2]找到最大子数组的长度，使得从 1 到 k 中至少有一个整数不存在。示例：对于 k = 3 和数组 = [1,2,1,1,2]，答案 = 5对于 k = 2 和数组 = [1,2,1,1,2]，答案 = 2。我的代码：def ans(A, n, k): #A is the array and n is the length    d = {}    if k > n:        return n    for i in range(n):        if A[i] in d:            d[A[i]].append(i)        else:            d[A[i]] = [i]    max_diff = 0    if len(d) != k:        return n    for j in d:        r = len(d[j])        if r == 1:            diff = max(n-d[j][-1]-1, d[j][0])        else:            diff = max(d[j][0], r - d[j][-1]-1)            for i in range(r-1):                diff = max(diff, d[j][i+1] - d[j][i]-1)        max_diff = max(max_diff, diff)    return max_diff但是，代码给出运行时错误和一些隐藏的测试用例的错误答案。可能的错误是什么？以及给出错误答案的可能测试用例？diff 的解释：基本上对于数组中的每个数字，它正在寻找延伸，即不存在该特定元素的间隔长度。对于第二个示例，d 变为 {1:[0,2,3], 2:[1,4]}。在二的情况下，在索引 0 上存在一个没有二的子数组，即长度 = 1，因此 diff 将为 1。那么在从索引 2 到 3（含）的子数组中没有二。因此，差异 = 2。编辑：考虑到评论，我对代码做了一些更改，它不再给出运行时错误，但我仍然对一些隐藏的测试用例有错误的答案。如果您想尝试问题链接：https://www.codechef.com/LRNDSA02/problems/NOTALLFL

Answer 1

该代码给出了输入的错误答案：

k = 2
array = [1, 2, 2, 1, 2, 2, 2, 2, 2]

更改应该在第 18 行，即而不是

 diff = max(d[j][0], r - d[j][-1]-1)

它应该是

 diff = max(d[j][0], n - d[j][-1]-1)

这是一个小错误，但导致很多测试用例失败。

Answer 2

考虑以下：

目标 = @，所有其他数字 = -。

A = { - - - @ - @ @ - - - - - - @ - @ - - - - - - - - - - - }

如果我们想找到不包含@的子数组，我们可以将整个数组视为被@包围，这样：

A` = { @ - - - @ - @ @ - - - - - - @ - @ - - - - - - - - - - - @ }

然后，这只是一个问题 - 跟踪最后遇到的@的位置，以及连续两次出现的@之间的最大差异。@ 可以是 1..k 之间的任何数字，因此可以通过大小为“k”的数组来跟踪它。

C++ 代码类似于（请测试 off-by-1 错误，因为我希望它在那里：

int subarr(int* A, size_t n, int k)

{

   if (n < k)

   {

      return n;

   }

   size_t max = 0;

   std::vector<size_t> lastPos(k);

   for (size_t i = 0; i < lastPos.size(); i++)

   {

      lastPos[i] = -1;

   }

   // Find the longest subArray when excluding a single digit of the digits present.

   for (size_t i = 0; i < n; i++)

   {

     if ((i - lastPos[A[i]]) > max)

     {

        max = i - lastPos[A[i]];

     }

     lastPos[A[i]] = i;

   }

   // Check for last

   for (size_t i = 0; i < lastPos.size(); i++)

   {

     if ((i - lastPos[A[i]]) == -1)

     {

        return n;

     }

   }

   return max - 1;

}