48.最长不含重复字符的子字符串.md

最长不含重复字符的子字符串

题目

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

数据范围: 长度小于40000

示例1

输入："abcabcbb"
返回值：3
说明：因为无重复字符的最长子串是"abc"，所以其长度为 3。

示例2

输入："bbbbb"
返回值：1
说明：因为无重复字符的最长子串是"b"，所以其长度为 1

示例3

输入："pwwkew"
返回值：3
说明：因为无重复字符的最长子串是 "wke"，所以其长度为 3。

思路 & 解答

这道题，可以使用哈希表解决，使用哈希表主要是为了保存字符最后一次出现的索引位置，同时记录开始索引位置start和最长的不包含 重复字符的子字符串长度len;

遍历每个字符，当发现map包含该字符的时候，如果该字符上次出现的位置不在``start之后，那么不用更新start`,否则`start`需要更新为上次出现该字符的位置。

遍历字符的时候，同时将每个字符以及它出现的索引位置，添加到map里面，计算当前的最长的不包含 重复字符的子字符串长度len，与之前保存的进行对比即可。

Java代码实现如下：

import java.util.HashMap;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    int lengthOfLongestSubstring(String s) {
        int start = -1, len = 1;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {

                start = Math.max(start, map.get(s.charAt(i)));
            }
            map.put(s.charAt(i), i);

            len = Math.max(len, i - start);
        }
        return len;
    }
}

C++代码如下：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int start = -1, len = 1;
        unordered_map<char, int> myMap;
        for (int i = 0; i < s.length(); i++) {
            if (myMap.count(s[i]) > 0) {
                start = max(start, myMap[s[i]]);
            }
            myMap[s[i]] = i;
            len = max(len, i - start);
        }
        return len;
    }
};

时间复杂度：遍历一次所有的字符，O(n)

空间复杂度：使用额外的空间map，故为O(n)