สมมติว่าเรามีอาร์เรย์สองอาร์เรย์ขนาด m และ n งานคือการหาความยาวซับอาร์เรย์ขั้นต่ำในอาร์เรย์แรก ที่มีองค์ประกอบทั้งหมดของอาร์เรย์ที่สอง องค์ประกอบในอาร์เรย์ที่สองอาจมีอยู่ในอาร์เรย์ใหญ่ในรูปแบบไม่ต่อเนื่อง แต่วงต้องเหมือนกัน ดังนั้นถ้าสองอาร์เรย์เป็น A = [2, 2, 4, 5, 8, 9] และ B = [2, 5, 9] ผลลัพธ์จะเป็น 5 เนื่องจากซับอาร์เรย์เล็กที่สุดของ A จะเป็น [2, 4, 5, 8, 9] ที่นี่องค์ประกอบทั้งหมดเช่น [2, 5, 9] อยู่ในลำดับเดียวกัน ดังนั้นขนาดคือ 5
เราสามารถแก้ปัญหานี้ได้โดยการตรวจสอบว่าองค์ประกอบแรกตรงกับองค์ประกอบแรกของอาร์เรย์ที่สองหรือไม่ เมื่อองค์ประกอบแรกตรงกัน เราจะจับคู่องค์ประกอบที่เหลือของอาร์เรย์ที่สองในอาร์เรย์หลัก เมื่อองค์ประกอบทั้งหมดตรงกัน ให้อัปเดตความยาวหากจำเป็น หลังจากทำสิ่งนี้แล้ว คืนค่าความยาวขั้นต่ำของซับอาร์เรย์
ตัวอย่างโค้ด C++
#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);
}
ผลลัพธ์
Minimum length of subarray: 3
