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

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.36.59.14 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Soft_Job/M.1670044767.A.CB1.html ※ 编辑: brucetu (114.36.59.14 台湾), 12/03/2022 13:42:39