LeetCode 刷题 [C++] 第3题.无重复字符的最长子串

题目描述

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

题目分析

可以使用滑动窗口加哈希表来实现：

1. 使用start和end两个变脸来表示滑动窗口的头部位置和尾部位置，两者开始均为0；
2. 借助哈希表来记录已经遍历的字符的位置，以及len为滑动窗口的长度；
3. 按序遍历字符串，并判断哈希表中是否存在当前字符：
   • 如果存在当前访问的字符，且该字符上次出现位置大于start，即当前滑动窗口出现了相同字符，此时，更新start位置，并更新len为新窗口的长度；
   • 否则，则不更新start位置
4. 记录或者更新当前字符的位置，end和len分别加1，并且更新ans为max(ans,len);

Code

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int start = 0, end = 0, len = 0, ans = 0;
        int size = s.size();
        unordered_map<char,int> hash_map;
        while (end < size) {
            char tmp = s[end];
            if (hash_map.count(tmp) > 0 && hash_map[tmp] >= start) {
                start = hash_map[tmp] + 1;
                len = end - start;
            }
            hash_map[tmp] = end;
            ++end;
            ++len;
            ans = ans > len ? ans : len;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20