做网站需要的信息seo技术经理
本篇博客讲解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,