无重复字符的最长子串

杨比轩 · · 675 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

这道题难度中等:

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

示例 1:

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

示例 2:

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

示例 3:

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

解题思路:

  • 设置start标志位和index标志位,index从前往后依次遍历
  • 每次出现的字母,都缓存其最后一次出现的索引
  • 如果index指向的字母的lastLndex在start前面,也就是小于start
  • 如果当前字母的的lastIndex大于或者等于start,则start标志位移动到index的前面一位
  • 每次遍历都更新lastIndex和maxLength

这题就很正常,go的实现无论是内存还是速度,都远块于java。

java实现:

public static int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> charIndex = new HashMap<>(s.length());
    int start =0, maxLength = 0, length = 0;
    for (int i =0; i < s.length(); i++) {
        Character ch = s.charAt(i);
        Integer lastIndex = charIndex.get(ch);
        if (Objects.nonNull(lastIndex) && charIndex.get(ch) >= start) {
            start = lastIndex + 1;
            length = i - start + 1;
        } else {
            length += 1;
        }
        maxLength = length > maxLength ? length : maxLength;
        charIndex.put(ch, i);
    }
    return maxLength;
}

golang实现:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:杨比轩

查看原文:无重复字符的最长子串

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

675 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传