LeetCode：无重复字符的最长子串

佚名 5年前 (2020-03-09) 算法 576人围观抢沙发百度已收录

LeetCode：无重复字符的最长子串

利用滑动窗口获得字符串无重复最长子串

No.3 无重复字符的最长子串

题目：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

示例 1:

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

示例 2:

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

示例 3：

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

滑动窗口

时间复杂度：\(O(n)\)

空间复杂度：\(O(min(m,n))\)

滑动索引控制 [ i，j ）区间，用 Set 判断重复

public int lengthOfLongestSubstring(String s) {
    int len = s.length();
    int i = 0, j = 0, sum = 0;
    Set set = new HashSet();
    while (i < len && j < len) {
        if (set.add(s.charAt(j))) {
            j++;
            sum = Math.max(sum, j - i);
        } else {
            set.remove(s.charAt(i++));
        }
    }
    return sum;
}

穷举所有组合

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

空间复杂度：\(O(min(m,n)\)

以每一位为起始点，从起始点向后判断，用 Set 判断重复

public int lengthOfLongestSubstring(String s) {
    int length = s.length();
    HashSet set = new HashSet();
    char[] chars = s.toCharArray();
    int sum = 0;
    if (length == 1) {
        return 1;
    }
    for (int i = 0; i < length - 1; i++) {
        set.add(chars[i]);
        for (int j = i + 1; j < length; j++) {
            if (set.contains(chars[j])) {
                break;
            } else {
                set.add(chars[j]);
            }
        }
        sum = Math.max(set.size(), sum);
        set.clear();
    }
    return sum;
}