難度: Hard
目前下列解法的時間複雜度: O(m+n)
題目說明
給定兩字串 s 及 t 長度分別為 m 及 n。
求最小長度的 s 子字串,使得所有在 t 中出現的字元都在此子字串中出現且出現次數 >= 該字元在 t 中出現的次數。
解法: 兩個指針一加一減刷過去
0. 先算一下 t 幾個字元、每個字元出現的次數,直接存陣列。
1. 訂好左右指針,右邊的指針刷過去把上面陣列存的次數減少;左邊的增加。
2. 當次數都歸 0 時比一下長度,比較短就記下來。使用"總共還剩幾個字元"的方式避免刷 一次字元集合。
source code
然後想說用指標寫,結果還是到 4ms 。Q_Q