题目链接

剑指offer
leetcode

示例

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

解题思路

思路

• 标签：滑动窗口
• 定义一个 map 数据结构存储 (k, v)，其中 key 值为字符，value 值为字符索引位置
• 定义不重复子串区间的开始位置为 start，结束位置为 end
• 固定start不动， end 向后遍历。当end遇到重复字符，start应该放在「上一个重复字符的位置的后一位」，同时记录最长的长度
• 无论是否更新 start，都会更新其 map 数据结构和结果 max。
• 时间复杂度：O(n)

note：
start = Math.max(start, map.get(element) + 1); 从重复的字符下一位开始继续查找

代码

class Solution {
        public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0)
            return 0;
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0;
        for (int start = 0, end = 0; end < s.length(); end++) {
            char element = s.charAt(end);//获得当前位置的字符
            if (map.containsKey(element)) {//遇见重复字符
                start = Math.max(start, map.get(element) + 1);//从重复的字符下一位开始继续查找
            }
            map.put(element, end);
            max = Math.max(max, end - start + 1);
        }
        return max;
    }
}