培训网网站源码谷歌搜索引擎首页

本篇博客讲解LeetCode热题100道滑动窗口篇中的两道题

第一道：无重复字符的最长子串

第二道：找到字符当中的所有字母异位词

第一道：无重复字符的最长子串

哈希+滑动窗口

class Solution {public int lengthOfLongestSubstring(String s0) {int[] hash = new int[128]; //自建哈希表，将字母放入哈希表，来判断是否重复int n = s0.length(),len = 0;char[] s = s0.toCharArray();for(int left = 0,right = 0; right < n; right++){hash[s[right]]++;while(hash[s[right]] > 1){hash[s[left++]]--;}len = Math.max(len,right-left+1);}return len;}
}

* 暴力解法就不说了，由于解法可以为同向双指针，因此我们用滑动窗口的思想。*/
/*** 题解：* 1.首先为了方便操作，我们将字符串转字符数组。* 2.自建一个拟哈希表，用来判断是否出现重复字母。int[] hash = new int[128];默认出现零次。* 3.“进窗口” 也就是hash[s[right]]++;在哈希表存字符。再在判断完是否重复，和长度之后令right++* 4.“出窗口“ 当出现重复字符的时候，我们可以将left移动到重复字符的后一位。*             while (hash[s[right]] > 1){*                 hash[s[left++]]--;*             }* 也就是这个操作。并让哈希表中对应字符出现次数--。* 在循环之外，此时必定没有重复字符出现。此时找到最大无重复字符长度，我们更新len的值。

第二道：找到字符当中的所有字母异位词

哈希+滑动串口

class Solution {public List<Integer> findAnagrams(String s0, String p0) {int[] hashS = new int[26]; //通过比较两个哈希表是否一样用来判断是否是异位词int[] hashP = new int[26];char[] s = s0.toCharArray();//字符串转数组，方便求解char[] p = p0.toCharArray();int m = s0.length(),n = p0.length(); //得到两字符串长度List<Integer> ret = new ArrayList<>();for (int i = 0; i < n; i++) {   //将p字符串扔进拟哈希表p。等待与拟哈希表s进行比较hashP[p[i] - 'a']++;}for (int left = 0,right = 0; right < m; right++) {hashS[s[right] - 'a']++;    //进窗口if(right - left + 1 > n){   //如果进多了，那么就出窗口。hashS[s[left++]-'a']--;}if (Arrays.equals(hashS, hashP)){ //此时窗口大小一定为p数组长度的大小。ret.add(left); //比较两哈希表是否一致，如果一致，就添加初始索引。}}return ret; //最终返回初始索引数组集}
}

题解： 

* 1.为了比较异位词，我们通过构建两个哈希表，将p字符串扔进表2.
* 2.在right<m的情况下，默认进窗口。hashS[s[right] - 'a']++;
* 3.进窗口后判断窗口大小是否大于p0字符串的长度，如果大于那么就出窗口
* 4.出窗口后，此时若表1等于表2那么直接ret.add(left);
* 5.循环结束之后，返回ret，