专栏首页爱写BugLeetCode 3: 无重复字符的最长子串

LeetCode 3: 无重复字符的最长子串

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。

示例 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(iCodeBugs),作者:爱写Bug

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 542:01 矩阵 01 Matrix

    Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each ...

    爱写bug
  • Leetcode 14:Longest Common Prefix 最长公共前缀

    Write a function to find the longest common prefix string amongst an array of st...

    爱写bug
  • LeetCode 151:给定一个字符串,逐个翻转字符串中的每个单词

    Given an input string, reverse the string word by word.

    爱写bug
  • LeetCode 828. 统计子串中的唯一字符(中心扩展)

    我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符,并返回唯一字符的个数。

    Michael阿明
  • leetcode474. Ones and Zeroes

    先是用深度优先遍历的思想进行了实现,结果很明显是超时了。接着采用动态规划的思想,其实这题就是背包问题的一个演化。假设已知道m个0和n个1能够从数组中前i个元素最...

    眯眯眼的猫头鹰
  • LeetCode120|二维数组中的查找

    在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断...

    后端Coder
  • day 08 文件操作

    f = open(文件路径,mode='模式',encoding='编码格式') 最最底层操作的是bytes,打开一个文件的时候获取到的是一个文件的句柄

    py3study
  • 详解Python中的逻辑运算符and or 和not

    其次,逻辑操作符and 和or 也称作短路操作符(short-circuitlogic)或者惰性求值(lazy evaluation):它们的参数从左向右解析,...

    紫旭Blog - blog.zixutech.cn
  • [LeetCode]Roman to Integer 罗马数字转化成整数 [LeetCode]Roman to Integer 罗马数字转化成整数

    链接:https://leetcode.com/problems/roman-to-integer/#/description 难度:Easy 题目:13....

    尾尾部落
  • DWORD WORD到INT的转换

    首先,如果是在网络传输、消息解析的情况下,要注意一下网络传送使用的是大端还是小端模式,这影响到我们的高低位的传输顺序。

    Rekent

扫码关注云+社区

领取腾讯云代金券