LeetCode3. Longest Substring Without Repeating Characters

用户1665735

发布于 2018-06-20 08:54:35

53200

代码可运行

文章被收录于专栏：kevindroidkevindroid

运行总次数：0

代码可运行

题目

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

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, 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.

找出一个字符串的不含有重复字符的最长子串，注意，子串需要连续而子序列不需要。

解题思路

这题的思路很明显是动态规划，O(n^2)的方法很容易想到，即用一个bool类型的二维数组表示一个子串是否是非重复子串，然后一路递推就可以，但这明显不是我们想要的。可不可以一次便利得出结果？可以

public int lengthOfLongestSubstring(String s) {
        //指向正在遍历的字母的指针
        int start = 0;
        int end = -1;
        //指向最长的子串的开头结尾的指针
        int resStart = 0;
        int resEnd = -1;
        //指向上一个子串的指针
        int tmpStart = 0;
        int tmpEnd = -1;
        //用来存储不重复的字符，值表示字符所在位置
        HashMap<Character, Integer> set = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            //如果发现字符重复，进行一系列操作
            if (set.containsKey(s.charAt(i))) {
                //先保留这个子串，方便map删除
                tmpStart = start;
                tmpEnd = end;
                //如果正在遍历的子串长度大于之前的最大值，就替换
                if (end - start + 1 >= resEnd - resStart + 1) {
                    resStart = start;
                    resEnd = end;
                }
                //重新设置开始值为重复的字符的下一位
                start = set.get(s.charAt(i)) + 1;
                end = i;

                //如果与前一位相同，直接清空map
                if (s.charAt(i) == s.charAt(i - 1))
                    set.clear();
                else {
                    //否则仅清空相同位之前的字符
                    int index = set.get(s.charAt(i));
                    for (int k = tmpStart; k <= index; k++) {
                        set.remove(s.charAt(k));
                    }
                }
            } else {
                //不重复，直接向后遍历
                end++;
            }
            //把不重复的字符加入map
            set.put(s.charAt(i), i);
        }
        //因为存在最后一位字符所在的子串刚好是最长的可能，而这时又不会触发上方的语句，所以需要在结尾加个判断
        return resEnd - resStart + 1 > end - start + 1 ? resEnd - resStart + 1 : end - start + 1;
    }