MENU

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

September 18, 2018 • Read: 3002 • LeetCode阅读设置

题目链接: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;
    }
}
Last Modified: October 7, 2018
Archives Tip
QR Code for this page
Tipping QR Code