刚才的算法有问题,不能达到O(N),下面这个应该没问题
先遍历一次,记录S2每个char的位置
s1 = "ADOBECODEBANCBBCAA"
s2 = "ABC"
按顺序记录就行了不用管ABC
record是一个DOUBLE链表 0,3,5,9,10,12,13,14,15,16,17,18
下次遍历的时候用一个hashtable,记录位置,并且记录链表node的指针
只用遍历record的位置,并且record最小值
a b c
0 3 5
下面遍历链表中的9,发现hashtable有b,于是获得位置是3的b的指针,删除链表当中值为3的node,并且更新table
链表现在是 0,5,9,10,12.......
a b c
0 9 5
因为更新的不是最小值,所以不计算
下面是10,发现table已经有a,于是获得以前a的node指针,删除链表当中之前的a,更新table,计算当前节点值和head节点值的差,是5,于是不更新
a b c
10 9 5