LC0003 无重复字符的最长子串

1. 题目

无重复字符的最长子串

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

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

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

2. 解题思路

解法1

滑动窗口：当循环一个数组时，取2个索引i和j，都从0开始递增，通过i和j的变化，来获取所有的子数组。

这里，可以使用滑动窗口来获取子串，使用Set集合来判断子串元素是否重复。

使用滑动窗口先滑动j获取到子串S[ij)，如果S[ij)被认定为无重复，我们只需要检查S[j]是否存在于子串S[ij)中即可，若不存在，将S[j]存放在Set中，并将j往后移一位，如果存在，我们需要返回来判断S[ij)中，是哪一位与S[j]重复，这时，我们需要往前滑动i，再判断S[j]是否存在新的S[i，j)中，重复上面操作，直到循环结束。

解法2

滑动窗口优化

在循环时，我们保存值-索引到HashMap中，若不存在，将S[j]-j存放在HashMap中，并将j往后移一位，如果存在，取出存在的索引j'，直接跳过S[ij')，将i置为j'+1

3. 题解

解法1

int lengthOfLongestSubstringMethod1(String s) {
    //初始化滑动窗口索引i, j, 结果
    int i = 0, j = 0, result = 0;
    //新建HashSet存放子串
    Set<Character> set = new HashSet<>();
    //循环串
    while(i < s.length() && j < s.length()) {
        if(set.contains(s.charAt(j))) {
            //先删除i
            set.remove(s.charAt(i));
            //i往前滑动
            i ++;
        } else {
            //j存放到Set中
            set.add(s.charAt(j));
            //j往前滑动
            j ++;
            //计算结果
            result = Math.max(result, j - i);
        }
    }
    return result;
}

解法2

int lengthOfLongestSubstringMethod2(String s) {
    //定义结果
    int result = 0;
    //新建K-V存放元素-索引
    Map<Character, Integer> map = new HashMap<>();
    //循环数组
    for(int i = 0, j = 0; j < s.length(); j ++) {
        Character currentChar = s.charAt(j);
        if(map.containsKey(currentChar)) {
            //存在时，直接跳过i-j'
            i = Math.max(map.get(currentChar) + 1, i);
        }
        result = Math.max(result, j - i + 1);
        map.put(currentChar, j);
    }
    return result;
}

HashMap可以转为数组进行处理

int[26]：用于字母 ‘a’ - ‘z’ 或 ‘A’ - ‘Z’

int[128]：用于ASCII码

int[256]：用于扩展ASCII码

4. 分析

解法1

时间复杂度：O(n)

空间复杂度：O(n)

解法2

时间复杂度：O(n)

空间复杂度：O(n)

5. 知识点

滑动窗口

HashSet

HashMap

数组