LeetCode 3: 无重复字符的最长子串 Longest Substring Without Repeating Characters-阿里云开发者社区

开发者社区> 爱写Bug> 正文

LeetCode 3: 无重复字符的最长子串 Longest Substring Without Repeating Characters

简介: 题目: 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 Given a string, find the length of the longest substring without repeating characters. 示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
+关注继续查看

题目:

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

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

示例 1:

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

示例 2:

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

示例 3:

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

解题思路:

  • 暴力求解, 时间复杂度为 O(n^3), 因为要对所有字符遍历, 对子串遍历确认是否有重复字符, pass
  • 滑动窗口, 维护一个索引 [i,j) 的滑动窗口, 对已存在的字符 i' 直接更新滑动窗口 [i',j), 你需要保留每一个字符值及其索引, 即由字符映射索引位置

    • 哈希映射: Key 为字符值, Value 为索引位置
    • 字符映射: ASCII 码共 128 个字符, 维护一个长度为 128 的整型数组,数组索引值映射 128 个字符,存储元素值为字符位置

哈希映射:

Java:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();//转为字符数组
        if (chars.length == 0) return 0;
        HashMap<Character, Integer> map = new HashMap<>();//建立哈希映射
        int size = s.length(), count = 0, i = 0;
        for (int j = 0; j < size; j++) {//遍历字符
            if (map.containsKey(chars[j]))//如果映射中存在该字符
                i = Math.max(map.get(chars[j]), i);//更新滑动窗口的左边界 i
            count = Math.max(count, j - i);//更新 count 为最大值
            map.put(chars[j], j + 1);//更新映射中该字符映射的 Value 值为当前位置加一
        }
        return count + 1;//返回最大累加总数, 需要加 1
    }
}

Python:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
        hash_map = dict() # 建立字典
        size = len(s)
        i, count = 0, 0
        for j, c in enumerate(s): # 枚举字符
            if c in hash_map: # 如果映射中存在该字符
                i = max(i, hash_map[c]) # 更新滑动窗口的左边界 i
            count = max(count, j-i) # 更新 count 为最大值
            hash_map[c] = j+1 # 更新映射中该字符映射的 Value 值为当前位置加一
        return count+1 # 返回最大累加总数, 需要加 1

字符映射:

Java:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        if (chars.length == 0) return 0;
        int[] index = new int[128];//建立长度为 128 位的 ASCII 码字符映射表
        int size = s.length(), count = 0, i = 0;
        for (int j = 0; j < size; j++) {//遍历字符
            i = Math.max(index[chars[j]], i);//更新滑动窗口的左边界 i
            count = Math.max(count, j - i);//更新 count 为最大值
            index[chars[j]] = j + 1;//更新映射中该字符所在元素值为当前位置加一
        }
        return count + 1;//返回最大累加总数, 需要加 1
    }
}

Python:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
        size = len(s)
        i, count = 0, 0
        index = [0]*128 # 建立长度为 128 位的 ASCII 码字符映射表
        for j, c in enumerate(s): # 枚举字符
            i = max(i, index[ord(c)]) # 更新滑动窗口的左边界 i
            count = max(count, j-i) # 更新 count 为最大值
            index[ord(c)] = j+1 # 更新映射中该字符所在元素值为当前位置加一
        return count+1 # 返回最大累加总数, 需要加 1

因为 Python 没有字符概念, 需要 ord() 函数转为 ASCII 数字

欢迎关注微.信.公..众.号: 爱写Bug

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【前台 submit的重复提交 错误】submit的重复提交
错误表现: 会表现出来:ajax执行成功但是时而会进回调函数,时而不会进入回调函数。   分析原因: 页面的表达提交使用submit,然后又对这个提交按钮绑定一个点击事件,使用ajax来和后台进行交互,这个时候如果不return false;会导致ajax提交一次,submit提交一次,...
642 0
大厂高频面试真题详解:最长无重复字符的子串
大厂高频面试真题详解:最长无重复字符的子串
522 0
LeetCode 345. 反转字符串中的元音字母(JAVA)
编写一个函数,以字符串作为输入,反转该字符串中的元音字母。
127 0
【leetcode刷题】45. 同构字符串——Java版
⭐欢迎订阅《leetcode》专栏,每日一题,每天进步⭐ java 通过map的 k-v 解决 ——leetcode此题热评
11 0
+关注
爱写Bug
欢迎关注公众号:爱写Bug
85
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载