每日一题 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<>();

方法：

1. put(); 向哈希表中添加键值，接受两个参数：键和值，如果存在键则会更新值
2. keySet(); 获取哈希表中所有键的集合，返回一个Set集合
3. size(); 返回键值的数量
4. get();获取对应键的值
5. remove(); 删除key对应的键值
6. containsKey();判断映射的指定的键是否存在
7. containsValue();判断映射的指定的值是否存在