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

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

普通思路解法（模拟过程）：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int max = 0;
        int count = 0;
        int point = 0;
        int index = 0;
        Map<Character, Integer> map = new HashMap<>();

        int len = s.length() - 1;

        while(point <= len && index <= len) {
            char c = s.charAt(index);
            if(!map.containsKey(c)) {
                map.put(c, index);
                count++;
                index++;
            } else {
                if(count > max) {
                    max = count;
                }
                count = 0;

                point++;
                index = point;

                map.clear();
            }
        }

        if(count > max) {
            max = count;
        }

        return max;
    }
}

滑动窗口解法：

维护一个符合要求的窗口，每次找到重复的就左移到已记录的重复字符的下一个位置，未找到就右移，记录符合要求的最长子串。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0) {
            return 0;
        }

        int point = 0;
        int max = 0;
        Map<Character, Integer> map = new HashMap<>();

        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int cIndex = map.getOrDefault(c, -1);
            if(cIndex != -1) {
                point = Math.max(point, cIndex + 1);
            }

            map.put(c, i);
            max = Math.max(max, i - point + 1);
        }

        return max;
    }
}