题目描述

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

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

解析

滑动窗口算法

滑动窗口算法用于对给定的大缓冲区或数组的特定窗口大小执行所需的操作(即在遍历大缓存区或数组时, 对其特定的窗口大小执行特定操作)。目的是将很少出现问题的嵌套for循环转换为单个for循环，从而降低时间复杂度。例如: 找出某数组中和最大的子数组， 规定子数组元素个数为3， 即窗口大小为3， 当然窗口大小也可以是动态的。具体过程如下：

代码实现

实现一

• 时间复杂度: O(2n)=O(n)，最糟糕的情况下，每个字符要被i，j分别访问一次
• 空间复杂度: O(min(m, n))，滑动窗口法需要 O(k)的空间，其中 k表示 Set 的大小。而 Set 的大小取决于字符串 n 的大小以及字符集 / 字母 m 的大小

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int record = 0,i = 0,j = 0;  // record记录最长子串长度
        int length = s.length(); 
        Set strSet = new HashSet();  // 使用HashSet作为滑动窗口
        while(i < length && j < length){
            if(!strSet.contains(s.charAt(j))){  // s.charAt(j)不在strSet中
                strSet.add(s.charAt(j));
                j++;
                record = Math.max(record, j - i);
            }else{
                strSet.remove(s.charAt(i));
                i++;
            }
        }
        return record;
    }
}

实现二

该实现是对滑动窗口的优化，即在窗口中存在与当前元素相同的字符，直接把窗口左端移动到相同字符的后一位，而不是一步一步的移动左端窗口。

• 时间复杂度: O(n)，单单j会遍历n次
• 空间复杂度: O(min(m, n))

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length = s.length(), record = 0;
        Map<Character,Integer> map = new HashMap<Character,Integer>();
        for(int i = 0, j = 0; j < length; j++){
            if(map.containsKey(s.charAt(j))){  // 包含了有相同字符
                i = Math.max(map.get(s.charAt(j)),i);  // 把i定位到存储在map中且与s.charAt(j)相同的字符的下一个索引位置
            }
            record = Math.max(record,j - i + 1);  // + 1是因为前面已经排除了相同字符, 遂可把s.charAt(j)字符加入参与长度计算 
            map.put(s.charAt(j), j + 1);  // 把s.charAt(j)索引+1是方便i的定位(定位到相同元素的后一位)
        }
        return record;
    }
}