LeetCode Problem 3: Longest Substring Without Repeating Characters

LeetCode Problem 3 Java 一解.

分析

需要注意的是, 这并不是一个时间复杂度最优的方法. 以下方法的时间复杂度为 $O(N^2)$.

本题不需要什么动态规划之类, 只需要最基本的模拟 (implementation). 观察本题的数据范围, 容易猜到本题的时间复杂度. 对于这种单一字符串寻找子串, 可以使用双指针的方法: 假设 left 指针一开始处于字符串最左侧, right 指针不断地向右移动, 途中维护一个无序集合 chars 存储子串每一个不同字符; 若遇到曾出现的字符, 则 left 指针不断向右移动直到该字符只出现一次. 理论上只需要将 left 直接移动到旧的 left 指针之后的字符串第一次出现该字符的位置的右侧一格, 但是需要注意的是这个 “移动” 过程中我们仍然需要不断维护无序集合 chars, 因此不能只修改 left 的值, 而是不断地确认是否需要从 chars 中移除元素.

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashSet<Character> chars = new HashSet<Character>();
        int result = 0;
        int left = 0;
        for (int right = left; right < s.length(); right++) {
            Character ch = s.charAt(right);
            if (chars.contains(ch)) {
                while (s.charAt(left) != ch) {
                    chars.remove(s.charAt(left));
                    left++;
                }
                left += 1;
            } else {
                chars.add(ch);
                result = Math.max(right - left + 1, result);
            }
        }
        return result;
    }
}