java - 寻找 double 子集的有效算法和子集在一起

Question

<分区>

Answer 1

考虑对给定的问题使用两点法。

• 将 A 中每个字符的计数存储在 HashMap 中 - HashMapA
• 在遍历数组 B 时维护两个指针，start 和 end。
• 维护另一个 HashMap 以存储出现在数组 B 中 [start, end] 范围内的字符数 - HashMapB

相同的共享 ideone 链接:https://ideone.com/vLmaxL

---

for(char c : A) HashMapA[c]++;

start = 0
for(int end = 0; end < B.length(); end++) {
  char c = B[end];
  HashMapB[c]++;
  while(HashMapB[c] > HashMapA[c] && start <= end) {
    HashMapB[ B[start] ]--;
    start++;  
  }
  if(end - start + 1 == A.length())
    return true;
} 

return false;