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

题目链接：LeetCode3展开目录

题解展开目录

首先定义一个 Map<Character,Integer> 用来保存当前字符最后一次出现的下标位置。再定义一个 pre 数组，用来保存以每一个字符为结尾的最长无重复字符的子串。

接下来可以这么想，假设遍历到了下标 i，i 位置对应的字符为 c，第一种情况，如果 c 从来没有在 Map 中出现过，并且 i 不为 0 (也就是说 c 不为首字符)，那么 per [i] = pre [i - 1] + 1，并且把 < c,i > 放入 Map 中。

第二种情况，c 出现在 Map 中，并且通过 Map.get (c) 得到 c 最后一次出现的位置记为 lastPos，记 aPos = lastPos + 1，unRepeatLen = per [i - 1]，bPos = i - unRepeatLen，如果 aPos >= bPos，则 pre [i] = i - aPos + 1，否则 pre [i] = i - bPos + 1，并且无论何种情况都要记得更新字符最后一次出现的位置

代码展开目录

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() == 0)
            return 0;
        Map<Character,Integer> pos = new HashMap<Character,Integer>();
        int[] pre = new int[s.length()];
        char[] str = s.toCharArray();
        for(int i = 0;i < s.length();i++) {
            Integer lastPos = pos.get(str[i]);
            if(lastPos == null) {
                pre[i] = i == 0 ? 1 : pre[i - 1] + 1;
                pos.put(str[i],i);
            } else {
                int aPos = lastPos + 1;
                int repeatLen = pre[i - 1];
                int bPos = i - repeatLen;
                if(aPos >= bPos)
                    pre[i] = i - aPos + 1;
                else
                    pre[i] = i - bPos + 1;
                pos.put(str[i],i);
            }
        }
        int max = pre[0];
        for(int i : pre)
            max = Math.max(max,i);
        return max;
    }
}