[数据结构与算法]LeetCode 3.无重复字符的最长子串

题目

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

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

解法

解法1

从字符串下标0开始,向右挪动指针.从指针开始遍历字符串,每一个char都存入set集合,如果add方法返回false,即改set集合的长度是从指针开始的最长子串,依次比较获得最大值,当子串长度+剩余长度>=字符串长度时就可以跳出循环了.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        int length = 0;
        for (int i = 0; i < chars.length; i++) {
            int repeat = isRepeat(chars, i);
            length = repeat > length ? repeat : length;
            if (repeat >= chars.length - i) break;
        }
        return length;
    }

    public int isRepeat(char[] chars, int index) {
        Set<Character> set = new HashSet<>();
        for (int i = index; i < chars.length; i++) {
            boolean add = set.add(chars[i]);
            if (!add) {
                break;
            }
        }
        return set.size();
    }
}

解法2

在解法1中进行改进,解法1中最小单位为char,在解法2中最小单位为string

采用快慢两指针,慢指针是当前遍历的索引,快指针是遍历字符串的进度,慢指针到快指针即当前的子串,如果快指针的下一个char没有在set集合中存在,即当前子串+1、快指针+1,如果存在即慢指针+1.

?? 代表快指针,? 代表慢指针

class Solution {
    public static int lengthOfLongestSubstring(String s) {
        if (s.equals("")) return 0;
        char[] chars = s.toCharArray();
        int length = chars.length;
        int max = 1;
        Set<Character> set = new HashSet<>();
        for (int i = 0, end = 0; i < chars.length; i++) {
            if (i != 0) set.remove(chars[i - 1]);
            while (end < length && !set.contains(chars[end])) {
                set.add(chars[end]);
                end++;
            }
            max = Math.max(max, set.size());
        }
        return max;
    }
}