[数据结构与算法]leetcode 3. 无重复字符的最长子串

题目

?

3. 无重复字符的最长子串

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

思路

? ?最长子串，开始我的思路是动态规划，但是经过思考后发现做不出来，于是看了题解，在这里写一下我的心得。方法名为滑动窗口，所谓窗口就是一个队列，我们的目的是找到最长子串，遍历给定的字符串s，维护一个队列，我们每次都要保证当前所遍历的元素入队，如果因为队列中包含这个元素而无法入队，那就出队到能把这个元素入队。我个人的理解就是贪心一点，新来的总是好的，无论如何也要把新来的加入进来，如果规则不允许就把之前的赶走。

代码

 public static int lengthOfLongestSubstring(String s) {
        //思路是滑动窗口，虽然并不太理解，但是还是能写的
        int max = 0;
        ArrayList<Character> arrayList = new ArrayList<>();
        for (int i = 0;i<s.length();i++){
            if(!arrayList.contains(s.charAt(i))){
                arrayList.add(s.charAt(i));
            }else {

                while (arrayList.contains(s.charAt(i))){
                    arrayList.remove(0);

                }
                arrayList.add(s.charAt(i));
            }
            max = Math.max(max,arrayList.size());
        }
        return max;
    }