LeetCode实战003 寻找最长不重复子串

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

示例 1:

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

示例 2:

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

示例 3:

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

题目解析

题目的关键在于，如何定义不重复、最长子串两个概念。

满足这个定义的字符串必须满足两个条件：

字符串是连续的, 也就是说，在这个串的左边和右边各增加一部分，就能得到原字符串，不能在中间增加任何字符。
字符串中所有字符都只能出现1次

解法：滑动窗口法

滑动窗口法是解决字符串处理问题的一个常用方法，特别适合处理这种“遍历子序列然后求值”的问题。

滑动窗口法的基本思想是，用i,j来表示当前关注的这个子串的起点和终点，那么子串就是 $[i, j)$ 这一段了（除了最初 $j = 0$ ），我们每次检查s[j+1]处的字符，如果它是不重复的，就让j向前滑动一个单位（也就是j++）；如果它重复了，那么就让i向前滑动一个单位，j不变，直到不重复为止。

可是，如果仔细想想，i如果每次只滑动一位，效率太低了！比如窗口内是aaaaaabbbbbbbbc下一个字符是c，那要等到i滑动多少次，j才能继续滑动啊，太慢了！

所以，就让i直接滑动到它该去的地方吧，假设字符s[j+1]与子串中的s[k]冲突，那么i就应该滑动到k+1这个位置！

OK，思路已经全部理清，现在来写代码吧！

int lengthOfLongestSubstring(string s) {
        int  n, i = 0, j, k, maxLen = 0;
        n = s.size();
        for (j = 0; j < n; j++) {
            for (k = i; k < j; k++){//检查是否有重复字符
                if (s[k] == s[j]) {
                    i = k + 1;//有重复，i跳到k+1，结束检查
                    break;
                }
            }
            if (j - i + 1 > maxLen)//看一下当前的子串是不是最长的
                maxLen = j - i + 1;
        }
        return maxLen;
    }

复杂度分析

这个解法的空间复杂度是 $O(1)$

时间复杂度，最坏的情况下是 $n^3$ , 但是在原题的测试用例下表现非常好，超过了99.5%的答案，比用stl还快！

用STL的解法

然而在一般情况下，stl的效率还是很高的，如果增加很多特例，stl的表现还是会更稳定一些，所以这里还是贴出STL代码供参考。

#include<iostream> 
#include<string>
#include<algorithm>
#include<map>
using namespace std;

class Solution {
public:
    /*
    滑动窗口法，i为窗口的起点，j为窗口的终点
    map的key-value对为（字符，字符被存入map时的j+1）后面这个值代表了遇到重复字符时，i应该跳到的位置
    j一直保持自增，i不自增，i的增长只靠窗口的滑动
    */
    int lengthOfLongestSubstring(string s) {
        int n = s.length(), maxLen = 0;
        map<char, int> map;
        for (int i = 0, j = 0; j < n; j++){
            if (map.find(s[j]) != map.end()) {
                //这里不用把跳过的字符全都删掉，如果s[j]是之前跳过的，map[s[j]]一定小于i，只要保持i不变就行，这样s[j]在后续的步骤就会像新字符那样处理
                i = max(map.find(s[j])->second, i);
            }
            maxLen = max(maxLen, j - i + 1);
            map[s[j]] = j + 1;
        }
        return maxLen;
    }
};

时间复杂度 $O(n)$

空间复杂度 $O(n)$