九章演算法 | Google 面試題：Minimum Cycle Section

撰文 | JZ

專欄 | 九章演算法

題目描述

給出一個int的數組 array, 求這個數組的最小循環節的長度。

思路點撥

可以考慮使用雙指針(L,R)，並開一個變數記錄len當前的循環節，由於循環節肯定是從第一位開始，所以用L記錄當前匹配到的位置，R一直往後移動，如果當前位不匹配，那麼L就重置，len就加1。整體複雜度O(n) 。

考點分析

這題是雙指針類型的變形，如果發現了循環節每次都是從第一個數開始這一個性質，那麼就可以根據這個性質設計出對應的雙指針做法，不過在細節上還需要仔細的斟酌一下。

九章參考程序

https://www.jiuzhang.com/solution/minimum-cycle-section/

推薦閱讀：