LeetCode03 无重复字符的最长子串

暴力解法，O(n²)

    public int lengthOfLongestSubstring(String s) {
        ArrayList<Integer> lenList = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            Set<Character> set = new HashSet<>();
            int count = 0;
            for (int j = i; j < s.length(); j++) {
                char c = s.charAt(j);
                if (!set.contains(c)) {
                    set.add(c);
                    count++;
                } else {
                    lenList.add(count);
                    break;
                }
                lenList.add(count);
            }
        }
        return MaxInList(lenList);
    }

    private static int MaxInList(ArrayList<Integer> list) {
        if (list.isEmpty()) {
            return 0;
        }
        int max = list.get(0);
        for (Integer num : list) {
            if (num > max) {
                max = num;
            }
        }
        return max;
    }

滑动窗口，O(n)

public int lengthOfLongestSubstring(String s) {
        HashSet<Character> set = new HashSet<>();
        int max = 0;
        int n = s.length();
        int right = -1;
        for (int left = 0; left < n; left++) {
            if (left != 0) {
                set.remove(s.charAt(left - 1));
            }

            while ((right + 1 < n) && !set.contains(s.charAt(right + 1))) {
                set.add(s.charAt(right + 1));
                right++;
            }
            max = Math.max(right - left + 1, max);
        }

        return max;
    }