Leetcode 3. Longest Substring Without Repeating Characters

解法1：

每次选取一个字符，从该字符开始往后遍历，存入HashSet中去，借助HashSet来判断是否重复出现，如果遇到重复字符，就结束循环，计算起始索引的长度，然后将HashSet清空，继续循环，再从第二个字符开始遍历，直到处理完所有字符。

此解法的时间复杂度是O(N^2)，最坏情况下时间复杂度是O(N^3)，因为HashSet的contains方法；空间复杂度是O(N)

解法2：

采用256大小的数组，利用

解法3：

滑动窗口算法。

此解法和上面的第一种解法有点类似，使用两个变量，一左一右，像窗口一样滑动，遇到重复值时，就将左边的一个字符从HashSet中移除，直到遍历完所有字符。

此解法的时间复杂度是O(N)，最坏情况下时间复杂度是O(N^2)，因为HashSet的contains方法；空间复杂度是O(N)。

解法如下：

如果使用hashset代替arraylist，速度会变快，arraylist应该可以保留substring

class Solution {

    public int lengthOfLongestSubstring(String s) {

        int left = 0;

        int right = 1;

        int n = s.length();

        int result = 1;

        ArrayList sl = new ArrayList();

        if (s.equals("")){

            System.out.println("empty string");

            return 0;

        }

        sl.add(s.charAt(0));

        while (left < n && right < n){

            char last = s.charAt(right);

            if (sl.contains(last)){

                left += sl.indexOf(last)+1;

                sl.subList(0, sl.indexOf(last)+1).clear();

            }

            sl.add(last);

            right += 1;

            result = Math.max(result, right-left);

        }

        

        return result;

    }

}