数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在C++中查找包含所有元素（按相同顺序）的最小子数组
假设我们有两个大小分别为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);
}输出
Minimum length of subarray: 3
更新于：2019年12月19日
240 次浏览
广告