[数据结构与算法]滑动窗口和unordered_set(哈希表)在字符串判断中的应用

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

这个题我一开始用到的是一个很常规的方法(实测我的方法还要优秀一点，无论是时间还是空间)，用ascII进行判断，从字符串下标0开始，查询每个下标的最长无重复字符字串，然后取最大值。我把最大值存在ans中，用的一个小技巧是当下标到字符串尾的长度小于ans时，就不需要进行判断了，因为不可能超过ans，节省了一点小时间。
哈希表的方法放在后面讲，

具体代码如下

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
    	//用来判断的字典，其实这里直接写一个={}也可以，但我想用下新学的memset初始化
    	//memset赋值会快一点，
        int adjust[129];
       	//头文件为string，记住这个用法就可以了,（首地址，要赋的值，大小）
        memset(adjust,0,sizeof(adjust));
        int n=s.length(),ans=0;
        int i=0;
        //前面提到的小技巧
       while(i+ans<n)
       {
           int start=i;
           //没有重复的话就向后找
           while(start<n&&adjust[s[start]]!=1)
           {
               adjust[s[start]]++;
               start++;
           }
           //留下最大的
            ans=max(ans,start-i);
            //每次结束之后重置adjust数组
            memset(adjust,0,sizeof(adjust));
            i++;
       }
       return ans;
    }
};

使用哈希表（即散列表）
先大致解释一下哈希表，关于哈希表的详细信息大家可以参考其他的文章（其实我想转载的，但是怕不能不告知转载）大致就是一个使用内存换取查找时间的方法，我上面的那个用于判断的adjust[129]就可以看成一个简单的哈希表（没使用散列函数），但是实际应用中，可能还需要一个散列函数，负责节省空间，即通过一个函数将值映射到内存中，可以减少内存使用。同时由于减少了内存的使用，还需要处理因为函数导致的数据冲突。听起来有点难用

幸运的是stl中有已经写好的哈希表可以使用，这里用到的是unordered_set。
创建方法unordered_set(type) name
插入值name.insert(value)
删除值name.erase(value)
返回值的个数name.count(value)。

判断字符是否出现过的方法已经有了，接下来就是处理技巧滑动窗口。当出现重复的元素时，我们一直将先左边的元素移除，直到表中没有重复的元素，这时表中剩下的元素就都是不重复的元素了，就可以继续查找了
其实我考虑想把滑动窗口应用到第一个方案中，但是写了几次还没写好，就先放一会儿，等以后补上吧

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
    	//建立无序表（功能就是哈希表）
        unordered_set<char> adjust;
        //左值先赋值为-1
        int left=-1,right=0,n=s.length(),ans=0;
        while(right<n)
        {
        	//从左边拆值（未发现重复元素前不许要拆值，即第一次）
            if(left>=0)
            {
                adjust.erase(s[left]);
            }
			
			//未发现重复元素时，从右边放入元素
            while(right<n&&!adjust.count(s[right]))
            {
                adjust.insert(s[right]);
                right++;
            }
            left++;
            ans=max(ans,right-left);
        }
        return ans;
    }
};

567. 字符串的排列
     给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
     换句话说，s1 的排列之一是 s2 的 子串 。
     示例 1：
     输入：s1 = “ab” s2 = “eidbaooo”
     输出：true
     解释：s2 包含 s1 的排列之一 (“ba”).

计算排列，可能第一个会想到next_permutation。但是这个只需要比较字符串的数量就好了，模板vector可以很方便的比较两个数组相同，所以采用他作为容器。都是小写字母，直接取26，再用s[i]-'a’就可。
在考虑做法，滑动窗口，不符合的时候就将最左边的移除，右边装入一个，只要相等就直接返回true，当右边装入了s2的最后一个元素还没相等的话，直接返回false。

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int len1=s1.length(),len2=s2.length();
        //当s1比s2长时，显然不包含
        if(len1>len2)
        {
            return false;
        }

        vector<int> adjust(26);
        vector<int> cc2(26);

        for(int i=0;i<len2;i++)
        {
        	//先把s1和与s1等长的s2字符段填入数组adjust和cc2中
            if(i<len1)
            {
                adjust[s1[i]-'a']++;
                cc2[s2[i]-'a']++;
            }else
            {
                if(cc2==adjust)
                    {
                        return true;
                    }

                cc2[s2[i-len1]-'a']--;
                cc2[s2[i]-'a']++;
            }
        }
        
        if(cc2==adjust)
        {
            return true;
        }
        return false;
    }
};