O(nk) 时间内的动态规划函数
Dynamic programming function in O(nk) time
给定两个大小为 n 的整数数组 A 和大小为 k 的 B，并且知道所有项目
在数组 B 中是唯一的，我想找到一个算法来找到索引 j' < j''，例如
B 的所有元素都属于 A[j' : j''] 并且值 |j''-j'| 被最小化或
returns 如果根本没有这样的索引，则为零。我还注意到 A 可以包含重复项。
为了更清楚，我们可以考虑数组 A = {1, 2, 9, 6, 7, 8, 1, 0, 0, 6} 和 B {1, 8, 6}，然后你可以看到 B ⊆ A[1 : 6] 和 B ⊆ A[4 : 7]，但同时 7−4 < 6−1，
因此算法应该输出 j'= 4 和 j''= 7.
我想找到一个运行时间为 O(nk) 的算法。
到目前为止，我的工作是考虑每个 j'∈[n]，我可以计算最小值 j'' ≥ j' 使得 B ⊆ A[j', j'']。如果我假设 B = {b1, ..., bk}，让 Next[j'][i] 表示最小索引 t ≥ j' 以便 at = b_i，即之后的下一个元素的索引a_j'（包括在内）等于 bi。
特别是如果这样的 t 不存在，只需让 Next[j'][i] = ∞。如果我能够证明最小的j''如下
j'' = Next[j'][i] 的最大 i∈[k],
然后我想我将能够设计一个动态规划算法来在 O(nk) 时间内计算 Next。非常感谢对此动态规划问题的任何帮助！
只是 运行 一个滑动 window 保持包含 B 的所有元素的不变性。这是 O(n) 和哈希图。
给定两个大小为 n 的整数数组 A 和大小为 k 的 B，并且知道所有项目 在数组 B 中是唯一的，我想找到一个算法来找到索引 j' < j''，例如 B 的所有元素都属于 A[j' : j''] 并且值 |j''-j'| 被最小化或 returns 如果根本没有这样的索引，则为零。我还注意到 A 可以包含重复项。
为了更清楚，我们可以考虑数组 A = {1, 2, 9, 6, 7, 8, 1, 0, 0, 6} 和 B {1, 8, 6}，然后你可以看到 B ⊆ A[1 : 6] 和 B ⊆ A[4 : 7]，但同时 7−4 < 6−1， 因此算法应该输出 j'= 4 和 j''= 7.
我想找到一个运行时间为 O(nk) 的算法。
到目前为止，我的工作是考虑每个 j'∈[n]，我可以计算最小值 j'' ≥ j' 使得 B ⊆ A[j', j'']。如果我假设 B = {b1, ..., bk}，让 Next[j'][i] 表示最小索引 t ≥ j' 以便 at = b_i，即之后的下一个元素的索引a_j'（包括在内）等于 bi。 特别是如果这样的 t 不存在，只需让 Next[j'][i] = ∞。如果我能够证明最小的j''如下
j'' = Next[j'][i] 的最大 i∈[k],
然后我想我将能够设计一个动态规划算法来在 O(nk) 时间内计算 Next。非常感谢对此动态规划问题的任何帮助！
只是 运行 一个滑动 window 保持包含 B 的所有元素的不变性。这是 O(n) 和哈希图。