剑指offer016-不含重复字符的最长子字符串

题目

给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子字符串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子字符串是 "b"，所以其长度为 1。

示例 3:

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

示例 4:

输入: s = ""
输出: 0

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

注意：本题与主站 3 题相同： https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

思路

一开始想到的就是滑动窗口，或者双指针。

双指针用起来很麻烦，建议用到双指针的时候，尽量用一层for循环，对i进行遍历

如果定义两个left和right，left和right的下标控制起来很麻烦，容易出现问题

一开始的想法当j指向第二个a的时候，i应该指向下一个元素b，此时从a-b内的元素应该从map中清除

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Map<Integer, Integer> map = new HashMap();
        int left = 0;
        int res = 0;
        for(int i = 0; i < n;i ++){
            Integer key = s.charAt(i) - 'a';
            if(map.containsKey(key)){
                int index = map.get(key);
                for(int j = left; j < index+1; j++){
                    map.remove(s.charAt(j)-'a');
                }
                left = index + 1;
            }
            map.put(key, i);
            res = Math.max(res, i - left + 1);
        }
        return res;
    }
}

• ← Previous Post
• Next Post →