leetcode 3.无重复字符的最长子串
思路:哈希表+滑动窗口
其实就是双指针和哈希表的综合运用而已.
为什么需要用哈希表呢?自己也是一步一步试出来的:我们如果暴力解的话,就是三重循环,超出时间限制;可以想到用双指针优化时间复杂度.但是,当我们在判断重复字符的时候,左指针和右指针指向的字符相同的时候,会想着把左指针移动,右指针不变,这样的话就没有什么重复元素的存在了.
但是,在pww这种字符的情况下,我们可以看到,上述方法是不成效的,因为这个时候左指针始终不移动,但是重复元素还是存在.导致变成了只和左指针指向的元素进行比较的局限性问题.因此这种方法不可取.
究其原因,.就是因为我们只比较了左指针指向的元素和右指针是否相同而已,而忽略了字符串的整体是怎样的.那么我们就会联想到,用哈希表来处理这个问题.既然不能暴力又想把这个字符串的整体都顾及到,就只能采用哈希.
做法就是用左右指针进行遍历,将遍历过的元素下标存储到哈希表中.
哈希的作用就是储存每个已经遍历过的元素的位置下标,一旦我们再次遍历到一个元素,这个元素在哈希表中已经有对应的存储,我们就需要把左指针移动到哈希表存储的这个元素的下标处,然后计算这个时候的字符串长度是多少.因为一旦有重复元素,说明在重复元素之前的元素就不能用了,我们就直接移动指针到这个元素上就可以了(题目中的子串是连续的).以此类推,边遍历,边判断,同时计算子串的长度.
class Solution {public int lengthOfLongestSubstring(String s) {Map<Character,Integer>map=new HashMap<>();int l=-1;int r=0;int res=0;while(r<s.length()){if(map.containsKey(s.charAt(r))){l=Math.max(l,map.get(s.charAt(r)));}res=Math.max(res,r-l);map.put(s.charAt(r),r);r++;}return res;}
}