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

原题

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

示例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是计入子串的)

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

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

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

代码

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/

发表评论

电子邮件地址不会被公开。