leetcode3-无重复字符的最长子串

彭晨涛 • 2019年12月26日 22:18 • 算法 • 阅读 10

原题

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

示例1：

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

示例2：

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

示例3：

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

解法

思想

滑动窗口，将出现的字符和下标在哈希表中对应起来。

该问题的关键是获取所有不重复字符子串的长度，比较出最大的长度，我们用last记录当前计算的子串的第一个字符位置。

那么不重复字符子串的长度的计算方法就是：

假设从last开始都是不重复字符，如果遇到一个在哈希集中出现过的字符并且是last或last之后的，说明遇到了重复字符，如下图的d，则此时的不重复字符子串adv的长度为第二个d之前的长度3-0=3。然后将last移到v上（第一个d后面的那个元素，这样新子串中就不会有两个d了），便可继续进行操作。

这样依次进行无重复字符子串的长度计算，当最后遍历到最后一个字符c的时候，都和last以及last之后出现的字符无重复，那么此时最后计算的子串vdfc的长度是5-2+1=4（因为c是计入子串的）

那么假设最后一个字符是v，当最后遍历到最后一个字符v的时候，和当前子串中的v重复了(vdfv)，那么和之前计算子串长度的方法一样是5-2=3（最后一个v不计入长度）

代码

Java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> map = new HashMap<>();
        int max = 0;
        int last = 0;
        char[] chars = s.toCharArray();
        for(int i = 0;i<chars.length;i++){
            if(map.containsKey(chars[i])&&map.get(chars[i])>=last){
                if(i-last>=max) max = i-last;
                last = map.get(chars[i]) + 1;
            }else if(i == chars.length-1&&i-last+1>=max){
                max = i-last+1;
            }
            map.put(chars[i],i);
        }
        return max;
    }
}

Go（2020/07/05）

func lengthOfLongestSubstring(s string) int {
    start := 0
    max := 0
    m := map[byte]int{}
    for i,c := range []byte(s){
        if v,ok := m[c]; ok && v >= start{
            if i-v > max { max = i-v }
            start = v + 1 
        }else{
            if i-start+1 > max {max = i-start+1}
        }
        m[c] = i
    }
    return max
}

go需要注意，如果需要兼容中文字符串，需要怎么处理：

func lengthOfLongestSubstring(s string) int {
    start := 0
    max := 0
    m := map[rune]int{}
    for i,c := range []rune(s){
        if v,ok := m[c]; ok && v >= start{
            if i-v > max { max = i-v }
            start = v + 1 
        }else{
            if i-start+1 > max {max = i-start+1}
        }
        m[c] = i
    }
    return max
}

Python

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        m = {}
        start = 0
        maxLen = 0
        for i,c in enumerate(s):
            v = m.get(c)
            if v != None and v >= start:
                maxLen = max(i-v,maxLen)
                start = v+1
            else:
                maxLen = max(i-start+1,maxLen)
            m[c] = i
        return maxLen

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode3-%e6%97%a0%e9%87%8d%e5%a4%8d%e5%ad%97%e7%ac%a6%e7%9a%84%e6%9c%80%e9%95%bf%e5%ad%90%e4%b8%b2/

leetcode3-无重复字符的最长子串

原题

解法

思想

代码

Java

Go（2020/07/05）

Python

相关推荐

发表回复