用于查找具有双精度和子集的子集的有效算法

Question

我有两个带字母的数组。我想知道数组 A 是否包含在数组 B 中，如下所示：A 中的字母必须在数组 B 中彼此相邻出现，但不必以与数组 A 中相同的顺序出现。可以接受的示例

A = abcd B = hbadcg

A = aabc B = abcag

不被接受的例子

A = aabcd B = adcbga

A = abcd B = abcdg

我可以做的是检查 A 的每个变体是否是 B 中的子字符串。但我正在寻找更好的方法

Answer 1

考虑对给定问题使用两点方法。将 A 中每个字符的计数存储在哈希映射中 -&nbsp;HashMapA当我们遍历数组 B 时，维护两个指针，开始和结束。维护另一个哈希映射以存储出现在数组 B 中的 [start, end] 范围内的字符数 -&nbsp;HashMapB共享 ideone 链接：https&nbsp;://ideone.com/vLmaxLfor(char c : A) HashMapA[c]++;start = 0for(int end = 0; end < B.length(); end++) {&nbsp; char c = B[end];&nbsp; HashMapB[c]++;&nbsp; while(HashMapB[c] > HashMapA[c] && start <= end) {&nbsp; &nbsp; HashMapB[ B[start] ]--;&nbsp; &nbsp; start++;&nbsp;&nbsp;&nbsp; }&nbsp; if(end - start + 1 == A.length())&nbsp; &nbsp; return true;}&nbsp;return false;