Fantasy
0%

Leetcode 3-无重复字符的最长子串

发表于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

题意

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

示例 1：

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

示例 2：

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

示例 3：

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

思路

面试栽在了这道题上，当时糊涂了没想明白，决定重做一遍。

采用双指针，$i$ 和 $j$ 分别指向当前判断的子串的首尾。用map<char,int>保存字符上一次出现的位置+1，+1的原因是为了避免和map中当key不存在时，int默认值为0的情况冲突。同时维护遍历过程中的最大长度。

初始化 $i=0, j=1$，每次判断 $s[j]$ 在map中的值，会存在三种情况：

  1. $m[s[j]] = 0$：

    表示 $s[j]$ 尚未在 $s[0, j)$ 中出现过。

  2. $m[s[j]] - 1 < i$：

    表示 $s[j]$ 在 $s[0, i)$ 中出现过，但没有在 $s[i,j)$ 中出现过。

  3. $m[s[j]] - 1 \ge i$：

    表示 $s[j]$ 在 $s[i,j)$ 中出现过。

在第1、2种情况中， $s[j]$ 并没有出现在当前判断的子串内，因此可以被加入到子串中，同时判断最大长度是否可更新。

在第3种情况中，$s[j]$ 出现在了当前判断的子串内，设其位置为 $j’$ ，此时可直接使指针 $i=j’+1$，即令 $i=m[s[j]]$。因为当 $i$ 取 $[i, j’]$ 中任何值时，$s[i,j]$ 中都将存在重复字符。

无论上述哪一种情况，在判断完 $s[j]$ 后，都应更新使 $m[s[j]]=j+1$ ，同时使 $j$ 右移一位。循环上述过程直到 $j$ 遍历完 $s$ ，此时维护的最大长度即为答案，算法复杂度 $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
class Solution {
public:
    int lengthOfLongestSubstring(string str) {
        if (str == "")
            return 0;
        
        int s = 0, e;
        map<char, int> pos;//pos[ch]表示ch在str中出现的位置+1

        int ans = 1;
        pos[str[s]] = 1;

        for (e = 1; e < str.length(); e++) {
            if (pos[str[e]] - 1 >= s) 
                s = pos[str[e]];
            else
                ans = max(e-s+1, ans);
            pos[str[e]] = e + 1;
        }

        return ans;
    }
};