LeetCode 3.

题目描述

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是
"abc"，所以其
长度为 3。
示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是
"b"
，所以其长度为 1。
示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是
"wke"
，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，
"pwke"
是一个子序列，不是子串。

题目解析

1. 重点是子串，不是子序列，所以可以思考用滑动窗口来解决
2. 另外一个重点说无重复的，所以可以使用hashmap将字母和位置进行缓存。
3. 执行过程：
   当前字符串不在hashmap中，长度积累
   当前字符串在hashmap中时，长度为当前位置减去上次该字符出现的位置，得到公式
   ans = max（ans， i - map[s.charAt(i)] + 1）

代码

    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int ans = 0;
        int startIndex = 0;
        for(int i = 0; i < s.length(); i++) {
            if(map.containsKey(s.charAt(i))) {
                startIndex = Math.max(startIndex, map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i), i);
            ans = Math.max(ans, i - startIndex + 1);
        }
        return ans;
    }