LeetCode：3. Longest Substring Without Repeating Characters（找出最长子串没有重复字符）-蒲公英云

LeetCode：3. Longest Substring Without Repeating Characters（找出最长子串没有重复字符）

文章最前：我是Octopus，这个名字来源于我的中文名—章鱼；我热爱编程、热爱算法、热爱开源。

这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

相关文章：

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

文章目录:

java实现方法1：

python实现方法1：

java实现方法2：

python实现方法2：

源码地址：

题目描述：

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

示例 1:

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

示例 2:

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

示例 3:

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

来源：力扣（LeetCode）

java实现方法1：

/**
     * 最长无重复字符串
     *
     * @param s 字符串
     * @return 长度
     */
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() < 1) {
            return 0;
        }
        int length = s.length();
        int maxLength = 0;
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length + 1; j++) {
                String sub = s.substring(i, j);
                boolean flag = judgeNoRepeat(sub);
                if (flag) {
                    maxLength = Math.max(maxLength, sub.length());
                }
            }
        }
        return maxLength;
    }
    /**
     * 判断字符串有没有重复字符串
     *
     * @param sub 子字符串
     * @return 布尔值
     */
    private boolean judgeNoRepeat(String sub) {
        Set<Character> set = new HashSet<>();
        for (char ch : sub.toCharArray()) {
            set.add(ch);
        }
        return set.size() == sub.length();
    }

时间复杂度：O(n^2)

空间复杂度：O(n)

python实现方法1：

def length_of_longest_substring(self, s: str) -> bool:
        '''
            最大无重复字符串
        Args:
            s: 字符串
        Returns:
            长度
        '''
        max_length = 0
        for i in range(len(s)):
            for j in range(i + 1, len(s) + 1):
                sub = s[i:j]
                if len(set(sub)) == len(sub):
                    max_length = max(max_length, len(sub))
        return max_length

时间复杂度：O(n^2)

空间复杂度：O(n)

java实现方法2：

/**
     * 最长子字符串
     *
     * @param s 字符串
     * @return 长度S
     */
    public int lengthOfLongestSubstring2(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实现方法2：

def length_of_longest_substring(self, s: str) -> bool:
        '''
            最大无重复字符串
        Args:
            s: 字符串
        Returns:
            长度
        '''
        dict_map = {}
        left, max_length = 0, 0
        for i in range(len(s)):
            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