在C ++中查找包含相同顺序的所有元素的最小子数组

Z时代
2024-01-10
分类：综合

假设我们有两个大小为m和n的数组，任务是在第一个数组中找到最小长度的子数组，该数组包含第二个数组中的所有元素。第二个数组中的元素可以不连续的形式出现在大型数组中，但是顺序必须相同。因此，如果两个数组类似A = [2、2、4、5、8、9]，而B = [2、5、9]，则输出将为5。作为A的最小子数组，将为[ 2、4、5、8、9]。在这里，所有类似[2，5，9]的元素都以相同的顺序排列。因此大小为5。

我们可以通过检查第一个元素与第二个数组的第一个元素是否匹配来解决这个问题。当第一个元素匹配时，然后我们匹配主数组中第二个数组的其余元素，当所有元素都匹配时，然后根据需要更新长度。完成此操作后，返回子数组的最小长度。

示例

#include<iostream>
using namespace std;
int lengthMinSubarray(int A[], int n, int B[], int m) {
   int res = INT_MAX;
   for (int i = 0; i < n - m + 1; i++) {
      if (A[i] == B[0]) {
         int j = 0, idx = i;
         for (; idx < n; idx++) {
            if (A[idx] == B[j])
               j++;
            if (j == m)
               break;
         }
         if (j == m && res > idx - i + 1)
         res = (idx == n) ? idx - i : idx - i + 1;
      }
   }
   return res;
}
int main() {
   int A[] = { 5, 6, 5, 2, 7, 5, 6, 7, 5, 5, 7 };
   int B[] = { 5, 5, 7 };
   int n = sizeof(A)/sizeof(A[0]);
   int m = sizeof(B)/sizeof(B[0]);
   cout << "Minimum length of subarray: " << lengthMinSubarray(A, n, B, m);
}