Facebook 电面

白人小哥，上来简单自我介绍，然后coding, 题目是longest substring with at m

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

我去，现在FB也考非面经的hard题啦？

LC那道是at least K，你这道是at most K？

补充内容 (2016-10-2 06:10):
不好意思，看成baidu那道题了。。。

请问这题2 points + HashMap不已经是最优解了吗？还能怎么优化？

另外应该用HashMap存字符及对应频率吧？楼主只用HashSet就能做了？是打错字了吗？

我用的是array[]版的hashset, 原理和hashmap一样， 我觉得是最优解了，但他让我优化。后来我也用hashmap优化过，他不是很满意，最后时刻发现可以用一个count来统计现在distinct char的个数，勉强写完但没时间解释，也不知道是不是他要的结果，估计够呛。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

这还能怎么优化？。。
我假设你用的O(n)的解法。。双指针。。这没有优化余地了吧？。。最多你说map改成一个数组。。

用map的话不是可以直接调map.size()吗？

iPhD 发表于 2016-10-2 06:43
哦哦，懂了，你是每次遍历一遍数组去记录当前distinct char的个数是吗？最优解的确可以用一个count变量＋ ...

不记录下distinct elements怎么知道++还是--呢？感觉必须用hash啊

不需要记录频数，直接记录每个数的latest index就行