這個第一個做法一看就很簡單不會是N^2
如果是我會這樣嘗試跟面試官解釋
字串abccba
L
R
R一直往右跑 L視條件往右跑 但L永不超過R
所以R最多右移N次 L也最多右移N次
複雜度應該是2N
以上面為例
abccba
L
R
此時S={a,b,c}
這時候發現s[r]=c, 與S內的字元重複, L開始往右移直到沒有重複 即
abccba
L
R
此時S={}, L一共位移3次
之後R繼續往右走, 如遇重複則L要操作右移
但整個演算法跑完L最多不會移動超過N次
所以應該是O(N)
不知道這樣有沒有達到你(面試官)的要求?
如果面試官還是認為你錯
你該做的是聽他的建議改成下面這樣
因為你沒有能力解釋到他懂
面試官本來就有高手有白癡
有時候人的盲點就是覺得這個東西很簡單
所以在跟對方解釋的時候一兩句話帶過 以為對方一點就通
其實你的跟他的對答方式 有一點溝通不良
例如
Q1: 你這個 while 應該改成 if 才對，不然會是 O(N^2)
A1: 改成 if 的話會錯，因為我必須"一直"縮左界直到目前的 window 內沒有重複的字符
這時候你應該跟他討論的是 你的寫法不會是O(N^2)而不是if不if的問題
如我前面說的 很多人在跟對方解釋溝通的時候語焉不詳 一兩句話帶過以為對方懂他意思
面試官講這句話其實真正的意思是
"你的這段code看起來有兩個迴圈應該是O(N^2) 可能要把while改成if還是怎麼樣看看"
他的意思不是在說 "你把while改成if就會O(N) pass"
所以你回他 "改成 if的話會錯" 整個討論已經偏掉
這就是為什麼溝通很重要也很困難 常常有人開會討論半天沒重點
就是因為兩個人都不把話完整講清楚 一直互相誤導
第二個QA
Q2: 但你這個 for 是 O(N)，while 也是 O(N)，乘起來是 O(N^2)，我要 O(N) 的解
A2: 我的 l 不會超過 r，兩者都是最多從 0 跑到 N (l+=1 總共最多跑 N 次)，是分開
的不能用乘法
而且複雜度分析的本來就是 upper bound，你要說 O(N^2) 也對，但我的分析方法可以壓
到 O(N)
我看你的回答馬上就懂你要表達的意思 有點程度的工程師應該都懂
但是顯然你遇到的面試官是一個白癡
這時候你不能用這麼跳步驟快速簡單講重點的方式來跟他解釋
你應該在學校也遇過那種 明明很簡單但是他就聽不懂
一定要一步一步來才能聽懂的同學吧?
你現在遇到的就是那樣的人啊
你想要過他這關
只有兩個辦法
1.他說的都是對的 弄懂他需求 滿足他需求就好了
2.你的解釋溝通技巧超好 講到他能懂
基本上走路線1比較安全
如果你當初快速搞懂他只是不要那個while 然後兩三下改好code
他還會覺得你好溝通 寫code快速熟練呢
還不用浪費力氣跟他解釋半天
再補充一點
Q6: 我要的最優解是 O(N)，不是 O(2N) (然後繼續跳針回 Q2)，我覺得我們對算法複雜
度的理解不一樣
其實你後來給的下面那個解worst還是2N啊
abcdefgg
可見不要跟面試官爭 沒有好下場的