无重复字符的最长子串

 

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

示例 1:

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

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

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

思路

当我们找到重复字符时，我们可以直接跳过该窗口。 也就是说，如果s[j]在子字符串[i,j-1)范围内与s[J]重复，我们不需要逐渐增加i，

我们可以直接跳过s[i,J]范围内的所有元素，即将i变成J+1。

时间复杂度：O(n)

空间复杂度：O(min(m,n)),m是字符集的大小,set的大小取决于字符串n的大小以及字符集/字母m的大小。

public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring03("abcabcbb"));
    }
    public static int lengthOfLongestSubstring03(String s) {
        int n = s.length(), ans = 0;
        //创建map窗口,i为左区间，j为右区间，右边界移动
        Map<Character, Integer> map = new HashMap<>();
        for (int j = 0, i = 0; j < n; j++) {
            // 如果窗口中包含当前字符，
            if (map.containsKey(s.charAt(j))) {
                //左边界移动到 相同字符的下一个位置和i当前位置中更靠右的位置，这样是为了防止i向左移动
                i = Math.max(map.get(s.charAt(j)), i);
            }
            //比对当前无重复字段长度和储存的长度，选最大值并替换
            //j-i+1是因为此时i,j索引仍处于不重复的位置，j还没有向后移动，取的[i,j]长度
            ans = Math.max(ans, j - i + 1);
            // 将当前字符为key，下一个索引为value放入map中
            // value为j+1是为了当出现重复字符时，i直接跳到上个相同字符的下一个位置，if中取值就不用+1了
            map.put(s.charAt(j), j+1);
        }
        return ans;
    }

滑动窗口的

如果给一个例子"abcabcbb"，让你手动找无重复字符的子串，该怎么找？一个字符一个字符的遍历，比如a，b，c，然后又出现了一个a，那么此时就应该去掉第一次出现的a，然后继续往后，又出现了一个b，则应该去掉一次出现的b，以此类推，最终发现最长的长度为3。所以说，我们需要记录之前出现过的字符，记录的方式有很多，最常见的是统计字符出现的个数，但是这道题字符出现的位置很重要，所以我们可以使用HashMap来建立字符和其出现位置之间的映射。进一步考虑，由于字符会重复出现，到底是保存所有出现的位置呢，还是只记录一个位置？我们之前手动推导的方法实际上是维护了一个滑动窗口，窗口内的都是没有重复的字符，我们需要尽可能的扩大窗口的大小。由于窗口在不停向右滑动，所以我们只关心每个字符最后出现的位置，并建立映射。窗口的右边界就是当前遍历到的字符的位置，为了求出窗口的大小，我们需要一个变量left来指向滑动窗口的左边界，这样，如果当前遍历到的字符从未出现过，那么直接扩大右边界，如果之前出现过，那么就分两种情况，在或不在滑动窗口内，如果不在滑动窗口内，那么就没事，当前字符可以加进来，如果在的话，就需要先在滑动窗口内去掉这个已经出现过的字符了，去掉的方法并不需要将左边界left一位一位向右遍历查找，由于我们的HashMap已经保存了该重复字符最后出现的位置，所以直接移动left指针就可以了。我们维护一个结果res，每次用出现过的窗口大小来更新结果res，就可以得到最终结果了。
 

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int res = 0;//记录最长子串的长度
        int end=0,start=0;//记录开始和结尾的下标
        Set<Character> set=new HashSet<>();//使用set容器不重复
        while(start<n && end<n){
           if(set.contains(s.charAt(end))){//如果窗口右侧的字符已经存在
               set.remove(s.charAt(start++));//左侧窗口边界向右
           }else{
               set.add(s.charAt(end++));//如果窗口中无重复，窗口右侧向右滑动
               res=Math.max(res,end-start);//同时记录当前最大长度
           }           
        }
        return res;
 }
}
public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int res = 0;
        int end=0,start=0;
       Map<Character,Integer> map=new HashMap<>();
        for(;start<n && end<n;end++){
           if(map.containsKey(s.charAt(end))){
               start=Math.max(map.get(s.charAt(end)),start);//从有重复的下一个位置继续找
           }     
            map.put(s.charAt(end),end+1);//map每次更新
            res=Math.max(res,end-start+1);//结果每次更新
        }
        return res;