习题讲解 | Facebook, LinkedIn, Uber高频面试题Minimum Window Substring
Minimum Window Substring，不仅是Facebook, LinkedIn, Uber等公司的高频面试题，也是一道非常经典的Sliding Window的题目。
本期习题讲解，我们就来给大家讲讲这道题的解法，让你在面试中遇见类似的题目时，也可以轻松解答。
先一起来看看题目：
题目描述
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = “ADOBECODEBANC”
T = “ABC”
Minimum window is “BANC”.
Note:
If there is no such window in S that covers all characters in T, return the empty string “”.
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
考点解析
这道题目的考点涉及到Sliding Window算法，以及String 字符串、Hash Table 哈希表、Two Pointers 双指针等，是一道比较有难度的面试题，大部分情况下会在onsite中出现。
Sling Window的思路相对比较好想，但难点在于implementation。
很多同学在面试中，明明已经解释清楚了题目的算法，但在写代码的过程中，却容易出现很多细节问题，从而被面试官challenge。
所以，这个视频就想通过讲解一道经典的sliding window问题，告诉大家如何去表达sliding window的算法，并写出正确、优雅的代码。
接下来，我们有请Emma老师为我们详解这道题的答案：
主讲人：Emma老师
FLGU一线公司资深工程师
点击链接查看讲解视频：https://www.laioffer.com/zh/video/2018-03-12-76-minimum-window-substring/
解题思路
这道题目的整体思路是使用一个快指针，和一个慢指针。
快指针从左向右移动，目的是在每个快指针停留的位置，找到以其为结尾的最短满足要求的substring。在快指针向右移动的时候，慢指针也需要相应的向右移动。
这里我们之所以能够使用Sliding Window的算法，是因为，当快指针向右移动的时候，其对应的慢指针必然无需向左移动。
此题的重点在于：
如何来记录sliding window部分（两个指针之间），能比较有效的表示跟target string T匹配的情况，以此来决定慢指针向前移动多少个位置，并且让两个指针移动的时候开销最小。
具体细节和过程请观看视频的讲解。
代码实现
代码中需要注意的细节处理及时间、空间复杂度分析请观看视频讲解。
还想看更多习题讲解视频？
来Offer免费精品公开课视频
官网、YouTube同步上线！
https://www.laioffer.com/zh/videos/coding-interview
https://www.youtube.com/channel/UC12XyYzyyZwFiIgafl_Ga6w
每周更新
内容包括：
01
面试习题系列视频
前谷歌资深面试官为你
精讲FLAG高频面试题
https://www.laioffer.com/zh/videos/coding-interview
02
职场分享系列视频
https://www.laioffer.com/zh/videos/tech-talk
分享求职和晋升攻略
https://www.laioffer.com/zh/videos/career-development
03
技术讲解系列视频:科技领域精英为你讲解最新技术热点
https://www.laioffer.com/zh/videos/tech-talk
视频观看方式
1. 网站订阅
目前所有最新的公开课视频，均可在来Offer官网www.laioffer.com的“免费资源”菜单下观看和订阅。
订阅后，每期更新视频会及时发送到您的邮箱。
2. YouTube订阅
订阅来Offer官方YouTube频道，不错过每期更新。
最新视频
习题33.
Search in Rotated Sorted Array
Facebook, Microsoft, Bloomberg, Uber, LinkedIn 高频面试题
- 考点：数组、二分查找
- 难度：中等
习题243/244/245.
Shortest Word Distance
Facebook, LinkedIn 高频面试题
- 考点：哈希表、倒排索引、Design
- 难度：中等
— 关于我们 —
硅谷IT黄埔军校 — — 来Offer，是硅谷最具实力的高科技在线教育平台。
来Offer由清华CS校友和来自硅谷一线公司的资深高级工程师精英共同创立，秉承清华大学计算机人的传统，以严谨、认真的治学和科研精神，为学员提供IT培训、面试指导与职业发展咨询等一站式服务。
5年来，我们已成功帮助超过2000名学员拿到他们的dream offer！
查看完整offer榜单 (1–115周)，欢迎登陆来Offer官方网站： www.laioffer.com
查看课程请点击：www.laioffer.com
