试水刷题，先从简单的练起。

题目

3. 无重复字符的最长子串

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

示例 1:

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

示例 2:

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

示例 3:

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

解题思路

还是老样子，先画张图思路就差不多出来了：

图中构造了一个字符串s abcdbfghdaklm 作为输入，其中 b d a 三个字母重复出现。

那么我们先从 s[0] 开始遍历，遍历到 s[4] 的时候，发现 b 之前已经出现过了，此时得到子串 abcd 。

接下来如果继续向右拓展，就必须避开 s[1] ，也就是应当从 s[2] 开始，直到 s[8] 再次出现重复的字符 d 停止，得到子串 cdbfgh 。

和上面一样，现在需要避开和 s[8] 重复的 s[3]，也就是新的子串应当从 s[4]开始遍历；
遍历到 s[9] 时，字母 a 似曾相识，但是由于 s[0] 并不在当前的子序列内，无需理会；
这次一路畅通的遍历到了末尾，得到子串 bfghdaklm。

当然，实际中执行代码并不需要重新去做遍历，当 abcd 遇到了 b 的时候，可以知道 cdb 一定是一个无重复子串，并不需要重新开始循环，只需要把窗口移动一下即可（这实际上就是滑动窗口的思想）。

另外还有一个可优化的小地方，当剩余的字符数量，已经不足以组成比当前找到的最长子串更长的子串时，可以直接中止循环。

解答

Java 代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0, now_len = 0, max_len = 0;
        Map<Character, Integer> s_map = new HashMap<>();

        for (int right = 0; right < s.length(); right++) {
            if (max_len > s.length() - right + now_len)
                break;

            Character c = s.charAt(right);
            Integer c_pos = s_map.get(c);
            if (c_pos != null && c_pos >= left){
                //不需要重新回头数数
                now_len -= c_pos + 1 - left ;
                //左侧边界设置为新的值
                left = c_pos + 1;
            }

            s_map.put(c, right);
            now_len += 1;

            if (now_len > max_len)
                max_len = now_len;
        }

        return max_len;
    }
}