LeetCode3 无重复字符的最长子串

子串指的是连接在一起的子字符串，而子序列可以不用每个元素都挨在一起，只要满足元素的优先顺序即可。例如：pwwkew,其没有重复的子串可以是wke，kew，但是其没有重复的子序列可以是pwke。

题目描述

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

示例

示例1：

输入：“abcabcbb"

输出：3

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

示例2：

输入：“bbbbb”

输出：1

解释：因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例3：

输入： “pwwkew”

输出：3

解释：因为无重复字符的最长子串是 “wke”，所以其长度为 3。

提示：哈希表，双指针，字符串，Sliding Window(滑动窗口)

题目解析

  按照题目给出的提示，可以使用滑动窗口的技巧来写，滑动窗口技巧本身就是用于在字符串或数组中寻找连续的一些极值问题，例如这里的最长子串长度。现在的问题在于什么时候能够扩大滑动窗口的大小？很明显，当下一个字符和当前滑动窗口内的字符不一致的时候，应该扩大它。而又什么时候应该缩小滑动窗口的大小呢？即遇到重复的时候，应该将滑动窗口内重复的字符左边的元素全都删除，这个过程中只要记录滑动窗口的最大值就能得到正确的答案。

  滑动窗口在实现的时候一般都是使用左右指针来对滑动窗口的边界进行限定的，假设这里我们使用left来表示滑动窗口的左边界，right来表示滑动窗口的右边界，而滑动窗口的长度就是（right - left）。现在就将问题转化为什么时候增大left（缩小窗口），什么时候增大right(扩大窗口)，其过程和上面描述的一样。

解法一：

  代码实现时可以使用一些集合框架来保存滑动窗口中的数组，这样可以方便于我们判断某个元素是否在滑动窗口内，当然我们使用数组来保存，自行判断之后再删除要删除的数据也是可以的。使用set集合的代码如下：

class Solution {
    
    public int lengthOfLongestSubstring(String s) {
    
        if (s.length() == 0) {
    
            return 0;
        }
        int maxLen = 0;		//记录滑动窗口的最大值
        int left = 0, right = 0;	//滑动窗口的左边界和右边界
        Set<Character> set = new HashSet<>();
        while (left < s.length() && right < s.length()) {
    
            if (!set.contains(s.charAt(right))) {
    	//判断set集合里面是否有重复字符
                set.add(s.charAt(right));
                right++;	//滑动窗口中添加元素并且扩大滑动窗口的范围
                maxLen = Math.max(maxLen, right - left);
            } else {
    
                set.remove(s.charAt(left));	//该字符在里面会逐个移除到那个重复元素的位置为止
                left++;
            }
        }
        return maxLen;
    }
}

程序的运行结果：

解法二：

其实上述set集合所做的查找我们完全可以用自己写一个循环来替代的，而且也比较好理解，代码如下：

  class Solution {
    
    public int lengthOfLongestSubstring(String s) {
    
  		if (s.length() == 0) {
    
            return 0;
        }

        int maxLen = 1;		//如果后面程序会执行，则串s中至少有一个元素
        int left = 0, right = 1;
       while (right < s.length()){
    
            int index = -1;
            for (int j = right - 1; j >= left; j--) {
    	//模拟set集合查找元素的过程，从后往前查找当前重复出现元素的下标即可
                if (s.charAt(right) == s.charAt(j)) {
    
                    index = j;
                    break;
                }
            }
            if (index != -1) {
    
                left = index + 1;	//新窗口的左边界应该为重复元素的下一位
            }
            right++;
            maxLen = Math.max(maxLen, right - left);
       }
       return maxLen;
   }
}

  程序运行结果：由代码可以看出最差的时间复杂度应该为O(n2)的，而且遍历查找的性能也没有set集合中查找某一元素的性能好，因此要比使用set集合的方式慢挺多的。

解法三

  到这里我们已经可以发现解这道题问题的关键在于怎么样才能快速的从现有的滑动窗口中元素查找出与当前遍历元素相同的元素，上面两种方法查找的时间复杂度都是O(logn)和O(n)级别。而查找有一种更加快速的方式是使用哈希表，其在不冲突下可以达到O(1)的时间复杂度，快了很多。而题目中给出的字符串最多就只有256个，并且不存在冲突的情况出现，因此可以创建一个大小为256的数组，其下标就是对应字符的ASCII码的值，**而数组中保存的值是该字符最后一次出现的位置（从1开始，因为数组初始为0，保存索引值可能会导致代码运行不正确）**代码如下：

  class Solution {
    
    public int lengthOfLongestSubstring(String s) {
    
		if (s.length() == 0) {
    
            return 0;
        }
        int[] hash = new int[256];
        int maxLen = 0;
        int left = 0, right = 0;
        while (left < s.length() && right < s.length()) {
    
            char c = s.charAt(right);
            left = Math.max(left, hash[c]);		//获取当前字符在滑动窗口中最后一次出现的位置（这里就相当于上面的查找过程，直接 使用O(1)的时间复杂度搞定
            maxLen = Math.max(maxLen, right - left + 1);
            hash[c] = ++right;	//保留该元素最后一次出现的位置
        }
        return maxLen;
    }
  }

程序运行结果：

可以看出要比使用set集合几乎快了一倍哈~