LeetCode第三题，五个版本迭代优化带你吃透two pointers算法

作者 | 梁唐

大家好，我是梁唐。

今天给大家带来LeetCode第三题的题解——无重复字符的最长子串，题意等描述来源于力扣官网。

题意

给定一个字符串s，要求返回其中不包含重复字符的最长子串的长度。

样例

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

数据范围

• s由英文字母、数字以及符号和空格组成

解法

拿到题目首先分析题意，题意还是比较简单的，就是要找最长的不含有重复字符的子串。

枚举

很容易想到我们可以枚举，首先我们可以枚举出s的所有子串，然后再一一判断子串当中是否包含重复的字符。最后选择不含有重复字符的最大子串即可。

写出代码来的话大概就是这样：

int n = s.size();
maxi = 0;

bool check(string &s, int st, int end) {
    set<char> st;
    for (int i = st; i <= end; i++) {
        if (st.count(s[i])) {
            return false;
        }
        st.add(s[i]);
    }
    return true;
}

for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
        if (check(s, i, j) && j-i+1 > maxi) {
            maxi = j-i+1;
        }
    }
}
return maxi;

如果大家去提交就会发现，这样的代码无法通过测试。我们简单分析一下就会发现这个算法的复杂度太大了，因为我们里外里一共用了三重循环。两重循环用来枚举子串的开头和结尾，还有一重循环判断子串是否包含重复字符。

我们知道s的长度最大是1e4，

的量级下，计算复杂度大约是1e12这个量级，显然会严重超时，必须要进行优化。

怎么优化呢？首先我们可以想到，我们其实没有必要枚举子串的开头和结尾，只需要枚举开头，在保证不包含重复字符的前提下往末尾一位一位延伸，直到结束或者是遇到重复字符为止。这样的话，我们就可以去掉一重循环，复杂度可以降到

，1e8的量级勉强不会超时。

代码如下：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ret = 0;
        // 枚举子串开头
        for (int i = 0; i < s.length(); i++) {
            set<char> st;
            // 一位一位地加入字符，直到出现重复break
            for (int j = i; j < s.length(); j++) {
                if (st.count(s[j])) {
                    break;
                }else {
                    st.insert(s[j]);
                    ret = max(ret, j - i + 1);
                }
            }
        }
        return ret;
    }
};

two pointers

如果大家学过two pointers算法的话，会发现这题就是two pointers的模板题。所谓模板题就是只要简单套用算法就可以求解的题目。

two pointers算法翻译过来就是两指针算法，非常非常地简单，其实可以理解成区间维护算法。我们用两个变量i和j分别指向一段区间的开头和结尾，保证这个区间是以i开头、j结尾能够找到的最大合法区间。

然后我们把j往右移动一位，由于j移动了之后带入了新的元素s[j+1]，可能会导致区间合法性的破坏。

前面说了我们要保证区间是合法的，合法性破坏了我们需要想办法恢复它的合法性。我们可以移动i，把i也往右移动，弹出元素，直到区间恢复合法性。

比如移动之后i变动到了k，区间[k, j+1]是新的合法区间。两指针算法其实就是这样两个指针交替移动保证区间一直合法的算法。

算法是很简单，但是我们对于算法的分析却远远没有结束。其实稍微细想一下，会发现几个问题。第一个问题是，我们迭代的合法区间的第一个版本从哪里来？第二个问题是，如何可以保证我们一定能够找到最大的那个合法区间呢？第三个问题是这个算法的复杂度是多少？

第一个问题比较简单，很明显，对于本题来说，[0, 0]就是一个合法区间。对于只有一个元素的区间，一定是合法的。

第二个问题则困难许多，是一道证明题，也就是得证明我们的算法一定会覆盖最大的合法区间。怎么证明呢？我们可以利用一些前提条件。

我们前文当中有一个设定，[i, j]是以i为开头和以j为结尾所能找到的最大合法区间。当我们将j移动到j+1之后，找到的新的合法区间[k, j+1]，其中的k一定大于等于i。不然的话就和我们的假设矛盾了。可能大家会觉得有些乱，没有关系，我们可以简化一下只看变量j。我们很容易发现，不论j如何移动，当前的合法区间一定都是以j结尾能找到的最大合法区间。

我们枚举了所有的j，自然可以保证全局的最大合法区间也在其中。把这些都想明白了，其实代码就很好写了：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ret = 0;
        set<char> st;
        int l = 0, r = 0;

        for (r = 0; r < s.length(); r++) {
            // 判断区间是否非法
            if (st.count(s[r])) {
                // 如果非法，将区间左侧右移，弹出元素
                while (st.count(s[r])) {
                    st.erase(s[l++]);
                }
            }
            ret = max(ret, r-l+1);
            st.insert(s[r]);
        }
        return ret;
    }
};

two pointers算法的复杂度是O(n)，估计很多同学会觉得很奇怪。明明代码里用了两重循环，为什么还是O(n)的复杂度呢？

我们稍微分析一下就会发现，l和r都是递增的变量，并且每执行一次循环，都会触发l或者r的增加。由于l和r最多只能从0增到n，所以加起来就是2n次操作。所以虽然我们用了两重循环，但依然是一个O(n)的算法。

优化

在这个实现当中，我们是用了一个set判断字符是否出现重复。其实我们还有更快的做法，是可以优化的。因为题目当中明确说了，字符只会有英文字符以及标点符号和数字。也就是说出现的字符是一个char类型，我们都知道char类型本质是整型，它的范围不会超过256。

所以我们可以使用一个长度为256的数组来代替set，因为数组的查询以及修改速度更快，可以达到O(1)。

经过优化之后，我们的代码是这样：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ret = 0;
        int st[256] = {0};
        int l = 0, r = 0;

        for (r = 0; r < s.length(); r++) {
            // 判断区间是否非法
            if (st[s[r]]) {
                // 如果非法，将区间左侧右移，弹出元素
                while (st[s[r]]) {
                    st[s[l++]]--;
                }
            }
            ret = max(ret, r-l+1);
            st[s[r]]++;
        }
        return ret;
    }
};

但是到这里还没有结束，这段算法依然还有优化的空间。

我们看一下会注意到我们用到了两重循环，其实仔细思考一下会发现内部的循环是可以去掉的。怎么去呢？

首先，我们思考一下里面while循环的用途，是为了弹出区间左侧的字符，使得s[r]这个字符在区间当中不再出现，只有这样才能将s[r]加入区间。

其实我们完全可以用数组记录下区间里的每一个字符出现的位置，当出现冲突的时候，我们就可以直接找到合法的位置了。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ret = 0;
        int st[256];
        memset(st, -1, sizeof st);

        int l = 0, r = 0;

        for (r = 0; r < s.length(); r++) {
            char c = s[r];
            // st[c] >= l 即c字符在区间当中出现过
            if (st[c] >= l) {
                // 将l移动到c字符的后一位即可
                l = st[c] + 1;
            }            
            st[c] = r;
            ret = max(ret, r-l+1);
        }
        return ret;
    }
};

有几个细节需要注意一下，首先是数组st的初始化，全部初始化成-1，而不是0。因为0是有实际含义的，代表第0位的字符。其次是循环内部的判断，由于我们数组记录的不再是字符出现的次数而是字符出现的位置。

所以我们的判断条件也要修改，改成当前字符最后一次出现的位置是否大于现在的左侧边界l。如果最后一次出现的位置大于l，说明这个字符一定在当前的区间当中，也就是说会构成重复，需要移动l。很明显，要使得每个字符都不重复，l必须移动到该位置的右侧，最近的位置自然就是st[c] + 1。

虽然这道题不算很难，代码也很好写，但其中的思路以及一层一层优化迭代的技巧还是非常有价值的。因此非常推荐大家每一种解法都亲自试一试，体会一下其中的差别。

单纯地刷题是无法学好算法的，刷题之余的深入思考是必不可少的。

大家加油，与你们共勉！