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
}

(2024/3/24)

func lengthOfLongestSubstring(s string) int {
    start := -1
    end := -1
    var maxLen int
    charPos := map[byte]int{}
    for {
        end ++
        if end == len(s){
            break
        }
        lastPos, ok := charPos[s[end]]
        if !ok || lastPos < start{
            maxLen = max(maxLen, end - start)
        } else{
            start = lastPos
        }
        charPos[s[end]] = end
    }
    return maxLen
}

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/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年12月26日
下一篇 2019年12月27日

相关推荐

  • leetcode219-存在重复元素II

    原题 给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的绝对值最大为 k。 示例1…

    算法 2019年12月24日
    0160
  • leetcode542-01矩阵

    原题 给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的距离。 两个相邻元素间的距离为 1 。 示例1: 输入: 0 0 0 0 1 0 0 0 0 输出: 0 0 …

    2019年12月13日
    080
  • leetcode289-生命游戏

    原题 根据 百度百科 ,生命游戏,简称为生命,是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。 给定一个包含 m × n 个格子的面板,每一个格子都可以看成是一个细胞…

    算法 2020年4月2日
    0300
  • leetcode35-搜索插入位置

    原题 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 你可以假设数组中无重复元素。 示例 1: 输入: […

    算法 2020年3月2日
    0120
  • leetcode1144-递减元素使数组呈锯齿状

    原题 给你一个整数数组 nums,每次 操作 会从中选择一个元素并 将该元素的值减少 1。 如果符合下列情况之一,则数组 A 就是 锯齿数组: 每个偶数索引对应的元素都大于相邻的元…

    算法 2020年6月5日
    050
  • leetcode1114-按序打印

    原题 我们提供了一个类: public class Foo {   public void one() { print("one"); }   public void two() …

    算法 2020年2月1日
    0140
  • leetcode47-全排列II

    原题 给定一个可包含重复数字的序列,返回所有不重复的全排列。 示例: 输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ] 解法 思想 这道题…

    算法 2020年5月10日
    0100
  • leetcode365-水壶问题

    原题 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水? 如果可以,最后请用以上水壶中的一或两个来盛放取得的 z升…

    算法 2020年3月21日
    0190
  • leetcode1300-转变数组后最接近目标值的数组和

    原题 给你一个整数数组 arr 和一个目标值 target ,请你返回一个整数 value ,使得将数组中所有大于 value 的值变成 value 后,数组的和最接近 targe…

    算法 2020年6月14日
    0970
  • leetcode78-子集

    原题 给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。 说明: 解集不能包含重复的子集。 示例: 输入: nums = [1,2,3] 输出: [ [3…

    算法 2020年5月24日
    0310

发表回复

登录后才能评论