九章演算法 | Amazon 面試題：Find Substring

撰文 | JZ

專欄 | 九章演算法

題目描述

給定長度k，找出字元串str裡面所有長為k的子串。子串的字元不能重複，輸出滿足這樣條件的子串數量(子串相同的只算1個)。

思路點撥

用雙指針可以將所有的滿足條件的子串找出來，在去重方面可以採用字元串hash，也可以直接HashMap或者HashSet去重。

考點分析

本題主要考察雙指針，仔細分析一下，字元全是小寫字母，所有有效的字元串最多長度為26, 當k>26時直接輸出0，k<=26時用HashMap或者HashSet,複雜度O(n)。如果這題卡殼了，則需要好好的去刷刷雙指針的題目。

九章參考程序

https://www.jiuzhang.com/solution/find-substring/

推薦閱讀：