今日一题:LeetCode第三题:Longest Substring

题目：Given a string s, find the length of the longest substring without repeating characters.

简单说，给你一个字符串，找到其中最长的子串，该子串里没重复字母，返回其长度。

来两个例子：

例子1：

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

例子2：

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

分析一波：

按顺序从前往后遍历一遍字符串，对于其中每一个字母来说，当后面的字母和前面的所有字母都不重复的时候，说明子串可以继续增长，当有重复字母出现的时候，则记下来，说明该子串截止了。

举个栗子：给定字符串abcdaebff，遍历过程如下：

注意，上面的图里表示的是遍历到的每一个字母不能和之前正在累加的子串里的任意的字母重复，例如step3里f和前面的“cdaebf”里的f重复了，所以子串截至了。后面的d、a、e、b、f的遍历过程就不写了，大家理解这个挨个字母遍历并和之前累加的子串的所有字母比较的过程就可以了。

设计一波：

当以a为头，开始遍历字符串，此时设以a为头的子串为subA，则subA=“a”，然后下一个遍历到b，发现b与subA（此时subA=“a”）里的每个字母都不一样，所以subA要扩充了，subA=“ab”，然后遍历到c，发现c与subA（此时subA=“ab”）里的每个字母都不一样，则subA要继续扩充了，subA=“abc”，再按此逻辑继续遍历，一直到又出现了a，此时subA=“abcd”，发现有重复字母了，subA子串截止了，最终subA=“abcd”。对于以a为头的子串的寻找过程翻译成JAVA如下：

// 最终结果，返回最长无重复字母子串的长度
int length = 0;
// JAVA里查找重复字符的利器：HashSet或HashMap，查找时间复杂度O(1)
// 这里选用了HashSet
// 此时这个set可以理解为subA
Set set = new HashSet<>();
for (char c : s.toCharArray()) {
    // 如果发现有重复字母
    if (set.contains(c)) {
        break;
    }
    // 没有重复字母，则说明可以扩充进去
    set.add(c);
    length += 1;
}

此时length即subA的最终长度，下面再补充后面的从下个字母b为头开始查找，接着从c为头、从d为头、从a为头、从e为头、从b为头、从f为头、从f为头查找的代码，直接来个简单粗暴的subString，代码如下：

初版代码：增加3行~6行，22行~24行

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 这个是终止条件
        if (s.length() == 0) {
            return 0;
        }
        // 最终结果，返回最长无重复字母子串的长度
        int length = 0;
        // JAVA里查找重复字符的利器：HashSet或HashMap，查找时间复杂度O(1)
        // 这里选用了HashSet
        // 此时这个set可以理解为subA
        Set set = new HashSet<>();
        for (char c : s.toCharArray()) {
            // 如果发现有重复字母
            if (set.contains(c)) {
                break;
            }
            // 没有重复字母，则说明可以扩充进去
            set.add(c);
            length += 1;
        }
        // 把刚刚已经遍历完的a去掉
        s = s.substring(1, s.length());
        // 此时字符串变成了“bcdaef”（之前是“abcdaef”），再调一边这个方法，后面以此类推
        int subLen = lengthOfLongestSubstring(s);
        return Math.max(subLen, length);
    }
}

运行一下，结果如下：

只能说凑合着看吧。。。。。。 - -！！

可以看出性能离了个大谱，大家一眼就可以看出来是subString那一段的问题，这里要优化一下，简单说就是不要递归。大家可以想一下，在字符串abcdaebff中，在第一次发现a重复时，得到第一个无重复子串abcd，其实也意味着bcd也无重复字母，即我们把重复字段的前边一段去掉，剩下的也是无重复子串，只要继续按刚刚的方法扩充即可，这样说可能不太好理解，用上面图里step2举个栗子：

此时说明cdae并不用重新遍历了，“cdae”就是后面可能成为最长不重复子串的头。问题找到了，思路也有了，开始优化代码。当前计算length的方式就是简单的累加，即length++，不足以按刚刚的思路优化，所以我们改成算下标的长度，例如abcdaebff中第一个无重复子串abcd，长度为4，计算方式则如图：

那么我们就至少需要一个变量，存放head的坐标，然后后面扩充截止的时候就能用当前坐标去减head的坐标算出长度。改造后的代码如下：

最终版代码：

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 最终结果，返回最长无重复字母子串的长度
        int length = 0;
        // JAVA里查找重复字符的利器：HashSet或HashMap，查找时间复杂度O(1)
        // 这里改成选用HashMap，key为字母，Value为head坐标
        Map map = new HashMap<>();
        // 头坐标
        int head = 0;
        char[] ch = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            // 如果发现有重复字母
            Integer h = map.get(ch[i]);
            if (h != null) {
                // 子串截止，长度 = 当前坐标i - head
                length = Math.max(i - head, length);
                // head为重复的字母的坐标，且为最靠右的重复值的坐标，左边不看了，右面为下一次遍历计算长度用的head坐标
                head = Math.max(h + 1, head);
            }
            // 此时更新字母的最新坐标
            map.put(ch[i], i);
        }
        // 因为length只有在有重复字母的时候才会更新，所以最后一个不重复子串长度为s.length() - head
        return Math.max(s.length() - head, length);
    }
}

运行结果如下：

效果还可以，但是回头看看解释过程和思考过程，发现已经非常复杂了。并且有些不成体系，也就意味着这种解题思路只能作为针对这道题的个例来用，不能在后面的题目里举一反三，没有借鉴意义了，此时也说明我们没有抽象出这道题的关键点。再仔细回顾一下这道题目的内容及画的分析图，其实可以发现里面有很明显的滑动窗口，在后面使用的计算长度的方法里有很明显的双指针的影子，下面一篇我们通过滑动窗口、双指针的方式再系统性的剖析一下这道题目。

明天再写，美女图镇题：