leetcode算法入门Day6---滑动窗口

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

测试用例：

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

思路阐述：
  本题目我的想法时利用两个指针a,b分别指示子串的开头和结尾，同时利用map记录字串中元素的下标，b指向的字串未重复即未被map记录则b++。
  反之令a=map[b指向的字符]+1，最后比较 maxlength 与 b-a+1的大小，maxlength取其中较大的值
代码如下：

class Solution {
    public int lengthOfLongestSubstring(String s) {
       Map<Character,Integer> map=new HashMap();
       int maxlength=1;
       int start=0,end=1;
       if(s.length()==0)
       {
           return 0;
       }
       map.put(s.charAt(0),0);
       while(end<s.length())
       {
           if(map.containsKey(s.charAt(end)))
           {
               int n=map.get(s.charAt(end));
               while(start<n)
               {
                   map.remove(s.charAt(start));
                   start++;
               }
               start++;
               map.put(s.charAt(end),end);
           }
           else
           {
               map.put(s.charAt(end),end);
           }
           if(end-start+1>maxlength)
               maxlength=end-start+1;
        //    System.out.printf("%d %d %d\n",start,end,maxlength);
           end++;
       }
       return maxlength;
    }
}

 &emsp提交后通过了，但是效率只是中等，未达到80%以上，之后我研究了100%的大牛的提交代码，发现他的思路和我类似，但是实现的手段更加巧妙。

class Solution {
    public int lengthOfLongestSubstring(String s) {
            // 记录字符上一次出现的位置
        int[] last = new int[128];//优化一：全是字符串，128位的int数组空间利用并不大，但是其访问速度高于map的计算hash的实现
        for(int i = 0; i < 128; i++) {
            last[i] = -1;
        }
        int n = s.length();

        int res = 0;
        int start = 0; // 窗口开始位置
        for(int i = 0; i < n; i++) {
			//优化二，由于初始化中将s中所有字符的上一次index都赋予初值，可以直接调用，避免了对map中put的操作。
            int index = s.charAt(i);
            start = Math.max(start, last[index] + 1);//优化三：不需要刻意用i所在字符是否出现过，若未出现过last[index]+1=0必定小于start,反之一定>=start,start取其下一个;
            res   = Math.max(res, i - start + 1);//maxlength的取较大值
            last[index] = i;刷新index字符上一次出现位置
        }

        return res;
    }
}

567. 字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

测试用例:
输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

此题的想法是统计连续字符串中出现的字符数目，若存在满足字符数目与s1相同的长度为n的字串，则表示包含s1的排列。
  
思路阐述：
但是在实现的过程中，实现思路不清晰，起初希望使用两个数组记录s1的字符数目，同时利用双指针遍历s1待取到满足条件的j-i=s2.length的数组则返回成功，但是实现失败，查看了题解，基本思想相同，但是实现思路更简单。

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        for (int i = 0; i < n; ++i) {
		//分别记录s1,s2前s1.length的字符出现次数。
            ++cnt1[s1.charAt(i) - 'a'];
            ++cnt2[s2.charAt(i) - 'a'];
        }
		//若两个数组相同，表面s2的前s1.length的字串即为s2的排列
        if (Arrays.equals(cnt1, cnt2)) {
            return true;
        }
        for (int i = n; i < m; ++i) {
		//i从第n+1字符开始对数组s2进行一个记录，每次长度为n的窗口右移一个
            ++cnt2[s2.charAt(i) - 'a'];//右移最右端的字符出现次数+1
            --cnt2[s2.charAt(i - n) - 'a'];//右移最左端的字符退出窗口，所以i-n的位置--。
			//若窗口的次数与s1中字符次数相同，即窗口即为s1的排列。
            if (Arrays.equals(cnt1, cnt2)) {
                return true;
            }
        }
        return false;
    }
}