无重复字符的最长子串

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

示例一：

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

示例2：

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例3：

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

解题思路：

两个 for 循环 + 一个ArrayList进行实现

1. 进入第一个for(i)循环，i从0开始，先将i处位置的字符添加到list当中，list.add(s.charAt(i));
2. 进入第二个for(j)循环，j从i的后一个位置开始，也就是i+1，判断list中的元素包不包含此时j下标的字符
3. 如果不包含，说明没有重复，将此时j下标的字符加到list，list.add(s.charAt(j));
4. 如果包含,则说明字符在list中已经存在了，退出此次的for(j)循环
5. 将max和list.size()中较大的值赋给max：max=Math.max(max,list.size());
6. 将list清空，list.clear()，为下一次的循环做准备。

代码实现：

public int lengthOfLongestSubstring(String s) {
        int n=s.length();
        //先判断s的长度是否为0，s是否为空
        if(n==0 || s==null){
            return 0;
        }
        //max用来记录最大值
        int max=0;
        //list用来存放无重复的最长子串
        ArrayList<Character> list=new ArrayList<>();
        for(int i = 0; i<n; i++){
        	//先将i位置的元素存放进list
            list.add(s.charAt(i));
            //j开始的时候在i的后一个位置，也就是i+1
            for(int j=i+1;j<n;j++){
            	//list不包含j位置的字符时，说明没有重复，字符添加进list
            	//list包含j位置的字符时，说明有重复，直接break，退出本次循环
                if(!list.contains(s.charAt(j))){
                    list.add(s.charAt(j));
                }else{
                    break;
                }
            }
            //max始终记录的是无重复子串的长度
            max=Math.max(max,list.size());
            //将list清空,重新记录
            list.clear();
        }
        //最后返回max就行
        return max;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31