384. 最长无重复字符的子串

描述

给定一个字符串，请找出其中无重复字符的最长子字符串。

样例

例如，在"abcabcbb"中，其无重复字符的最长子字符串是"abc"，其长度为 3。
对于，"bbbbb"，其无重复字符的最长子字符串为"b"，长度为1。

挑战

O(n) 时间

思路

主要是利用两个指针解法

1. 利用map标记当前字符是否出现过
2. 对于当前 i ， j 一直往前遍历，直到出现重复为止
3. 对于出现重复的 j 就没必要继续往下遍历了，i 向前前进一格，同时将 hash 表中的 i 移除

代码

public class Solution {
    /**
     * @param s: a string
     * @return: an integer 
     */
    public int lengthOfLongestSubstring(String s) {
        int[] map = new int[256]; // map from character's ASCII to its last occured index
        
        int j = 0;
        int i = 0;
        int ans = 0;
        for (i = 0; i < s.length(); i++) {
            while (j < s.length() && map[s.charAt(j)]==0) {
                map[s.charAt(j)] = 1;
                ans = Math.max(ans, j-i + 1);
                j ++;
            }
            map[s.charAt(i)] = 0;
        }
        
        return ans;
    }
}