给定一个整数数组，找到最大子数组的长度，使得至少 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&nbsp;=&nbsp;{&nbsp;-&nbsp;-&nbsp;-&nbsp;@&nbsp;-&nbsp;@&nbsp;@&nbsp;-&nbsp;-&nbsp;-&nbsp;-&nbsp;-&nbsp;-&nbsp;@&nbsp;-&nbsp;@&nbsp;-&nbsp;-&nbsp;-&nbsp;-&nbsp;-&nbsp;-&nbsp;-&nbsp;-&nbsp;-&nbsp;-&nbsp;-&nbsp;}如果我们想找到不包含@的子数组，我们可以将整个数组视为被@包围，这样：A`&nbsp;=&nbsp;{&nbsp;@&nbsp;-&nbsp;-&nbsp;-&nbsp;@&nbsp;-&nbsp;@&nbsp;@&nbsp;-&nbsp;-&nbsp;-&nbsp;-&nbsp;-&nbsp;-&nbsp;@&nbsp;-&nbsp;@&nbsp;-&nbsp;-&nbsp;-&nbsp;-&nbsp;-&nbsp;-&nbsp;-&nbsp;-&nbsp;-&nbsp;-&nbsp;-&nbsp;@&nbsp;}然后，这只是一个问题 - 跟踪最后遇到的@的位置，以及连续两次出现的@之间的最大差异。@ 可以是 1..k 之间的任何数字，因此可以通过大小为“k”的数组来跟踪它。C++ 代码类似于（请测试 off-by-1 错误，因为我希望它在那里：int subarr(int* A, size_t n, int k){&nbsp; &nbsp;if (n < k)&nbsp; &nbsp;{&nbsp; &nbsp; &nbsp; return n;&nbsp; &nbsp;}&nbsp; &nbsp;size_t max = 0;&nbsp; &nbsp;std::vector<size_t> lastPos(k);&nbsp; &nbsp;for (size_t i = 0; i < lastPos.size(); i++)&nbsp; &nbsp;{&nbsp; &nbsp; &nbsp; lastPos[i] = -1;&nbsp; &nbsp;}&nbsp; &nbsp;// Find the longest subArray when excluding a single digit of the digits present.&nbsp; &nbsp;for (size_t i = 0; i < n; i++)&nbsp; &nbsp;{&nbsp; &nbsp; &nbsp;if ((i - lastPos[A[i]]) > max)&nbsp; &nbsp; &nbsp;{&nbsp; &nbsp; &nbsp; &nbsp; max = i - lastPos[A[i]];&nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; &nbsp;lastPos[A[i]] = i;&nbsp; &nbsp;}&nbsp; &nbsp;// Check for last&nbsp; &nbsp;for (size_t i = 0; i < lastPos.size(); i++)&nbsp; &nbsp;{&nbsp; &nbsp; &nbsp;if ((i - lastPos[A[i]]) == -1)&nbsp; &nbsp; &nbsp;{&nbsp; &nbsp; &nbsp; &nbsp; return n;&nbsp; &nbsp; &nbsp;}&nbsp; &nbsp;}&nbsp; &nbsp;return max - 1;}