ITPub博客

首页 > 应用开发 > Java > Java/Python:无重复字符的最长子串讲解

Java/Python:无重复字符的最长子串讲解

原创 Java 作者:千锋Python唐小强 时间:2019-12-20 16:17:40 0 删除 编辑

题目:

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


示例 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/Python:无重复字符的最长子串讲解

哈希映射:

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 数字


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/69923331/viewspace-2669529/,如需转载,请注明出处,否则将追究法律责任。

全部评论

注册时间:2019-05-14

  • 博文量
    886
  • 访问量
    470229