问题描述

最大不重复子串问题

解题思路

1. 方案一：借助Set判断是否有重复， 通过游标j巡回判断， 实际上是一种暴力破解的思路

   public static int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) {
            return 0;
        }
        int lengthOfRes = 0;
        Set<Character> set = new HashSet<>();

        int length = s.length();
        for (int i = 0; i < length; i++) {
            set.add(s.charAt(i));
            int j = i + 1;
            while (j < s.length() && !set.contains(s.charAt(j))) {
                set.add(s.charAt(j));
                if (j - i > lengthOfRes) {
                    lengthOfRes = j - i;
                }
                j++;
            }
            set.clear();
        }
        return lengthOfRes + 1;
    }

结果实际上很不理想, 时间复杂度处于后1/3, 内存占用更没法看了。内存占用这点实际上是在预期之内的

Runtime: 61 ms, faster than 22.26% of Java online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 39.3 MB, less than 20.73% of Java online submissions for Longest Substring Without Repeating Characters.

反思下这个算法性能浪费在哪里了？对于已经具备的计算结果利用率不高可能是关键问题。例如abcdeabc这个case， abcde作为一个整体是没有重复字符的，接下来遇到了字母a，我们可能只需要把“滑动窗口”向右平移就好了，而不是重置到字母b，重新计算bcde是否有重复。于是有了方案2

2. 方案二：

public int lengthOfLongestSubstring(String s) {
        int length = s.length();
        if (length <= 1) {
            return length;
        }
        int ans = 0;
        Map<Character, Integer> window = new HashMap<>(length);
        for (int i = 0, j = 0; j < length; j++) {
            char currChar = s.charAt(j);
            if (window.containsKey(currChar)) {
                i = Math.max(window.get(currChar)+1, i);
            }
            ans = Math.max(ans, j - i + 1);
            window.put(currChar, j);
        }
        return ans;
    }

这里最关键的是i = Math.max(window.get(currChar), i);这一句，这决定了窗口起始位置移动到哪里。
这个执行的结果大致如图：
，内存占用排名在前10%