LeetCode 3： Longest Substring Without Repeating Characters(最长无重复字符串)-蒲公英云

LeetCode 3： Longest Substring Without Repeating Characters(最长无重复字符串)

文章最前：我是Octopus，这个名字来源于我的中文名—章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人github ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

相关文章：

LeetCode：55. Jump Game（跳远比赛）
Leetcode：300. Longest Increasing Subsequence（最大增长序列）
LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）

文件目录：

题目描述：

java实现方式1：

python实现方式1：

源码地址：

https://github.com/zhangyu345293721/leetcode

题目描述：

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

示例 1:

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

示例 2:

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

示例 3:

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

来源：力扣（LeetCode）

java实现方式1：

/**
     * 最长无重复字符串
     *
     * @param s 字符串
     * @return 长度S
     */
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) {
            return 0;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        int left = 0;
        int length = 0;
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                left = Math.max(left, map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i), i);
            length = Math.max(length, i - left + 1);
        }
        return length;
    }

时间复杂度:O(n)

空间复杂度:O(n)

python实现方式1：

def length_of_longest_substring(s: str) -> bool:
    '''
        最大无重复字符串
    Args:
        s: 字符串
    Returns:
        长度
    '''
    dict_map = {}
    length = len(s)
    left = 0
    max_length = 0
    for i in range(length):
        if s[i] in dict_map:
            left = max(left, dict_map.get(s[i]) + 1)
        dict_map[s[i]] = i
        max_length = max(max_length, i - left + 1)
    return max_length