3. Longest Substring Without Repeating Characters 不重复的最长子串

题目：Longest Substring Without Repeating Characters 不重复的最长子串

难度：中等

Given a string, find the length of the longest substring without repeating characters.

Example 1:

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

Example 2:

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

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

题意解析：

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

解题思路一：

循环遍历所有的子字符串，获取最长的子字符串。

public int lengthOfLongestSubstring(String s) {
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            int count = 0;
            Map map = new HashMap();
            for (int j = i; j < s.length(); j++) {
                if (!map.containsKey(s.charAt(j))){
                    count++;
                    if (count>max){
                        max = count;
                    }
                    map.put(s.charAt(j),j);

                }else {
                    break;
                }
            }
        }
        return max;
    }

此算法进行了两次的遍历操作，时间复杂度为O(n²)，引用了额外的存储空间空间复杂度为O(n²)。

提交代码之后：

Runtime: 111 ms, faster than 12.06% of Java online submissions for Longest Substring Without Repeating Characters.

Memory Usage: 41.4 MB, less than 5.00% of Java online submissions for Longest Substring Without Repeating Characters.

可见效率非常低。

解题思路二：

定义一个变量max存储最大长度，定义一个map集合存储所有的字符，定义一个变量temp存储元素上一次重复的位置。遍历每一个字符之前首先判断map集合中是否有该字符存在，若存在则temp取已存在字符的最大的索引值。取当前元素与temp的差值，将这个差值和max作比较，取较大值赋值给max。

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

 

此算法进行了一次的遍历操作，时间复杂度为O(n)，引用了额外的存储空间空间复杂度为O(n)。

提交代码之后：

Runtime: 23 ms, faster than 74.03% of Java online submissions for Longest Substring Without Repeating Characters.

Memory Usage: 39.4 MB, less than 19.68% of Java online submissions for Longest Substring Without Repeating Characters.

较上个方法效率提升了一大截，但是还不是最快的方法。

解题思路三：

跟第二种有点相似，我们知道字符串都是由一个一个的字符所组成的，而字符总共有128个，那么我们就可以将所有的字符存在以字符的ascll码值为索引的位置。其他思路与上面类似。

public int lengthOfLongestSubstring(String s) {
        int n = s.length(), max = 0;
        int[] arr = new int[128];
        for (int j = 0, i = 0; j < n; j++) {
            i = Math.max(arr[s.charAt(j)], i);
            max = Math.max(max, j - i + 1);
            arr[s.charAt(j)] = j + 1;
        }
        return max;
    }

此算法的时间复杂度为O(n)，而空间复杂度这里是使用了一个128的int数组，空间复杂度为O(1)。

提交代码之后：

Runtime: 15 ms, faster than 99.12% of Java online submissions for Longest Substring Without Repeating Characters.

Memory Usage: 39.8 MB, less than 15.89% of Java online submissions for Longest Substring Without Repeating Characters.

较前面的效率又提升了一些。