LeetCode

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

题目描述

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

思路

最开始的想法是使用分治策略，将字符串s从 index = s.length() / 2 处划分为两个字串s1和s2，然后最长字串一定在s1，s2或者位于s1和s2之间，递归求解即可。

但是问题出在横跨s1和s2的字串的最大长度并不能够用O(n)的时间复杂度求解，只会使问题变复杂。

然后考虑使用滑动窗口策略，令l指向当前窗口的起始位置，r不断地向前试探，同时在试探的过程中用哈希表记录下已经出现的字符的位置。当r遇到一个在当前窗口内存在重复字符时停止，计算并更新窗口最大值记录，并将窗口的起始地址移动到冲突字符的下一个位置。

基本语句是r++，时间复杂度为O(n)

代码

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

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.length() == 0)
        return 0;
    if (s.length() == 1)
        return 1;
    int l = 0, r = 0;
    int max_len = 0;
    int chr[128];
    memset(chr, -1, sizeof(chr)); // 初始化所有元素为 -1
    while (r < s.length()) {
        if (chr[s[r]] != -1 && chr[s[r]] >= l) {
            // 发现重复字符且在当前窗口内
            max_len = max(max_len, r - l);
            l = chr[s[r]] + 1; // 移动左指针到重复字符的下一个位置
        }
        chr[s[r]] = r; // 更新字符的最新位置
        r++;
    }
    max_len = max(max_len, r - l); // 处理最后一个窗口
    return max_len;
    }
};