Giả sử chúng ta có hai mảng kích thước m và n, Nhiệm vụ là tìm mảng con có độ dài tối thiểu trong mảng thứ nhất, mảng đó chứa tất cả các phần tử nếu là mảng thứ hai. Phần tử trong mảng thứ hai có thể xuất hiện trong mảng lớn không liền kề nhưng thứ tự phải giống nhau. Vì vậy, nếu hai mảng giống như A =[2, 2, 4, 5, 8, 9] và B =[2, 5, 9], thì đầu ra sẽ là 5. Là mảng con nhỏ nhất của A, sẽ là [ 2, 4, 5, 8, 9]. Ở đây tất cả các phần tử như [2, 5, 9] đều theo cùng một thứ tự. Vì vậy, kích thước là 5.
Chúng ta có thể giải quyết điều này bằng cách kiểm tra sự phù hợp của phần tử đầu tiên với phần tử đầu tiên của mảng thứ hai. Khi phần tử đầu tiên khớp, sau đó chúng tôi khớp các phần tử còn lại của mảng thứ hai trong mảng chính, khi tất cả các phần tử khớp nhau thì cập nhật độ dài nếu cần. Sau khi thực hiện việc này, trả về độ dài tối thiểu của mảng con.
Ví dụ
#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);
} Đầu ra
Minimum length of subarray: 3