LeetCode之字符串系列

2018/10/27 leetcode

刷刷leetcode,锻炼代码思维~

003-longest SubString Without Repeating Characters

* Given a string, find the length of the longest substring without repeating characters.
* For example, the longest substring without repeating letters for "abcabcbb" is "abc",
* which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
public int lengthOfLongestSubstring(String s) {
    // 字符串输入不合法
    if (s == null) {
        return 0;
    }

    // 当前处理的开始位置
    int start = 0;
    // 保存结果
    int result = 0;
    // 访问标记,记录最新一次访问的字符和位置
    Map<Character, Integer> map = new HashMap<>(s.length());

    for (int i = 0; i < s.length(); i++) {
        char ch = s.charAt(i);
        // 如果字符已经出现过(在标记开位置算起),就重新标记start
        if (map.containsKey(ch) && map.get(ch) >= start) {
            start = map.get(ch) + 1;
        }
        // 如果没有出现过就求最大的非重复子串的长度
        else {
            result = Math.max(result, i - start + 1);
        }

        // 更新访问记录
        map.put(ch, i);
    }
    return result;
}

解题思路,核心思想——HashMap

具体设置两个标志位,start来记录初始位置,result记录长度

Search

    Table of Contents