【leetcode】Minimum Window Substring
2020-12-13 02:00
标签：hash 生活 工作 面试题 leetcode 以我们列举的生活场景为例，我们在具体做这件事的时候，肯定不会拿着老板给的类似T中：A物品 B物品 A物品 C物品 这么二的清单，而是对物品做统计，生成这样的需求清单：
【leetcode】Minimum Window Substring,搜素材,soscw.com 【leetcode】Minimum Window Substring 标签：hash 生活 工作 面试题 leetcode 原文地址：http://blog.csdn.net/shiquxinkong/article/details/26967915问题：
生活场景：
分析：
物品A：X件
物品B：Y件
物品C：Z件
而在寻找的过程中，我们还需要一份已收集清单，就是目前已经找到的每个物品的信息，其形式与上面列举的一致。那么这些信息怎么来存储呢，我们总是希望对给定的物品，在O(1)的时间内找出对应的数值信息，所以要用hash table。
我们开始在起始楼层(下电梯的楼层)向上查找，遇到一个物品，我们看下是否是我们需要的，若是，则收集，并更改已收集清单相应物品的数量上加1。若不是，则跳过，继续向楼上搜集。看到这里我们就发现了问题，因为我们看到物品是需要的就收集它，并更改已收集表，那么我们怎么判断我们已经完成了收集工作了呢？比较两个表中对于的项，已收集项都大于等于需求的时候？但这样要进行比较，不能在O(1)的时间得到明确的判断，所以我们还需要一个变量，来记录到目前为止，收集到的”有效“的物品数，何为有效的物品，比如需求里A：3，B：2，假设A的数量已经是3，当再次遇到A时，虽然A是需求清单里需要的，但是已经有3个了，满足要求了，现在遇到的A就不能算作有效的物品，你现在需要做的是去收集除A以外其他物品。当有效物品数与需求清单中的总物品数相等的时候，我们就说我们的收集工作完成了。
但是这时你又会想，有没有更好的选择，比如你是从1楼开始收集的，收集到10楼将物品收集完毕，从2楼或者更高的楼层开始收集是不是也能完成任务？这样就可以少爬几层楼梯。这就要判断1楼的物品性质了，假如1楼的物品不是需要的，当然可以直接从2楼开始，亦或者，虽然1楼的物品是需要的，但是2楼也有这个物品，而且从2楼开始，这个物品总是也满足要求。那么就可以从2楼开始，依次2楼，3楼，直到不能精简，这就是当前的一个精简窗口，也就是不包含子窗口的窗口。但这个就是最小的吗？不一定，因为可能从11楼开始，到13楼就收集齐备了。所以这个查找的过程要进行到最后。每次找到新的窗口，跟目前最小的比较，更新最小窗口。实现：
string minWindow(string S, string T) {
int N = S.size();
int M = T.size();
int minWindowLen = INT_MAX;
//hash table init all 0s
//used to statistic the number of each letter needed.
int needToFind[256] = {0};
for (int i = 0; i needToFind[S[start]])
{
if(hasFind[S[start]] > needToFind[S[start]])//redundant
hasFind[S[start]]--;
++start;
}
int windowLen = end - start + 1;
if (windowLen
文章标题：【leetcode】Minimum Window Substring
文章链接：http://soscw.com/essay/24672.html