leetcode-72

题面：

官方题解：

https://leetcode-cn.com/problems/minimum-window-substring/solution/zui-xiao-fu-gai-zi-chuan-by-leetcode-solution/

重点：

• 首先需要看懂官方题解，用滑动数组的方法，设置左指针left（0）和右指针right（-1），先让右指针增大，等到满足某一要求时，再让左指针增大，最后返回最小的窗口。

• 右指针right为什么要从-1开始？

  因为每次进入循环时，right都会加1，如果right从0开始，就会漏掉第0个元素，参考队列（queue）数据结构，队尾指针也是从-1开始。

• 如果按照官方题解的思想，然后自己写代码，需要经历三个阶段：

  1. 逻辑完全正确，只有最后一个测试用例超时。
  2. 逻辑完全正确，删去了很多无用的操作，把if-else的判断降低到最少，还是最后一个测试用例超时。
  3. 逻辑完全正确，采用官方题解中map的非理性写法，居然通过了。

• map非理性写法：

  需求：“将mp中key对应的value加1”

  非理性写法：mp[key]++

  非理性之处：不去判断mp中是否有key对应的键值对，上来就用自增运算符。

• 非理性写法通过的理由：

  1. 如果每次都判断mp中是否有key对应的键值对，需要使用find函数，find函数的时间复杂度为O(logN)，N为mp中元素的个数，而随着mp规模的增大，将会耗费大量时间，

  2. mp[key]++，如果mp中没有key对应的键值对，那么它会自动创建一个键值对，默认value值为0。

  3. 实验代码：

     #include 
     #include 
     #include 

 ```c++
 #include 
 #include 

源代码：

理性写法（FA）

//思想上和官方题解一模一样，但就是超时
class Solution
{
public:
    map tm;
    map sm;
    bool check()
    {
        for(map::iterator it = tm.begin(); it!=tm.end(); it++)
        {
            if(sm.find(it->first)!=sm.end())
            {
                if(sm[it->first]second)
                {
                    return false;
                }
            }
            else{
                return false;
            }

        }
        return true;
    }

    string minWindow(string s, string t)
    {
        int tLen = t.size();
        int sLen = s.size();
        for(int i=0; i

//采用非理性写法
class Solution
{
public:
    map tm;
    map sm;
    bool check()
    {
        for(map::iterator it = tm.begin(); it!=tm.end(); it++)
        {
//            if(sm.find(it->first)!=sm.end())
//            {
//                if(sm[it->first]second)
//                {
//                    return false;
//                }
//            }
//            else{
//                return false;
//            }
            //非理性之一 
            if(sm[it->first]second){
                return false;
             }

        }
        return true;
    }

    string minWindow(string s, string t)
    {
        int tLen = t.size();
        int sLen = s.size();
        for(int i=0; i