这个第一个做法一看就很简单不会是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
可见不要跟面试官争 没有好下场的