无重复字符的最长子串

问题陈述

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

示例：

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

思路分析

可使用滑动窗口解题，定义一个 map 数据结构存储 (k, v)，其中 key 值为字符，value 值为字符位置 +1，加 1 表示从字符位置后一个才开始不重复。

初始化start，end为窗口的首尾，皆指向字符串第一个字符；end++，在不出现重复的情况下将新元素加入map，并每轮记录当前窗口的最大值；若出现了重复，则start移动到该重复元素。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class solution{
    public int lengthOfsubString(String s){
        int n=s.length(),res=0;
        Map<Character,Integer> map=new HashMap<>();
        for(int start=0,end=0;end<n;end++){
            char curr=s.charAt(end);
            if(map.containsKey(curr)){
                start=Math.max(map.get(curr),start);//初始map.get(end)==0
            }
            res=Math.max(res,end-start+1);
            map.put(s.charAt(end),end+1);
        }
        return res;
    }
}