每日一题 Day1
每日一题 Day1
无重复字符的最长子串
第一印象
第一想法就是使用暴力解法，遍历出每个字符串再用条件筛选符合要求的字符串，时间复杂度为O(N^2)。
滑动窗口与哈希表
滑动窗口（双指针）多用于处理字符串与序列的操作，根据题目的要求，求解串中符合某种条件的序列的最长或者最短的长度。
在本题中即窗口中不包含重复的字符，以右指针的移动更新左指针的边界。
public int lengthOfLongestSubstring(String s) {
Map<Character,Integer> dic = new HashMap<>(); //创建滑动窗口对应的哈希表
int i=-1,j=0,len=s.length(),res=0;//定义左右指针，初始化字符串长度，最长字串的长度
while(j<len){ //开始循环
if(dic.containsKey(s.charAt(j))){
i=Math.max(i, dic.get(s.charAt(j))); //判断，如果右指针的字符存在于哈希表中，则必须将左指针的边界移动到重复字符的下一个字符上
}
dic.put(s.charAt(j),j); //如果不重复则更新字符和索引到哈希表中
res=Math.max(res,j-i);//更新最大子串的长度
j++;//右指针后移
}
return res;
}
哈希表的Java使用
创建实例：Map<Element,Element> hashmap = new HashMap<>();
方法：
- put(); 向哈希表中添加键值，接受两个参数：键和值，如果存在键则会更新值
- keySet(); 获取哈希表中所有键的集合，返回一个Set集合
- size(); 返回键值的数量
- get();获取对应键的值
- remove(); 删除key对应的键值
- containsKey();判断映射的指定的键是否存在
- containsValue();判断映射的指定的值是否存在