leetcode挑战: “无重复字符的最长子串”之易水解决方案

<< 更多leetcode题目

题目链接

https://leetcode.cn/problems/longest-substring-without-repeating-characters/

难度

中等

C++解决方案

class Solution {
public:
    // 计算从位置 start 开始不重复字符的最大长度
    int uniqueChars(string s, int start)
    {
        int len = 0;
        vector<char> chars;
        for (int i = start; i < s.size(); i++)
        {
            char c = s[i];
            // 检查此字符是否在前面出现过
            if (find(chars.begin(), chars.end(), c) == chars.end())
            {
                chars.push_back(c);
                len++;
            }
            else
            {
                break;
            }
        }

        return len;
    }

    int lengthOfLongestSubstring(string s) {
        int m = 0;
        // 依次遍历每个字符，计算最大长度
        for (int i = 0; i < s.size(); i++)
        {
            int len = uniqueChars(s, i);
            m = max(m, len);
        }

        return m;
    }
};

解题思路

如果只是要实现这道题目的要求，难度并不大。 易水的上述实现方案采用的是最笨的方法：遍历字符串，从某一位置开始、计算其后不重复字符的最大长度。

总结

上述方式虽然能实现功能，但此方法的时间复杂度为 O(n^2)，空间复杂度为 O(n)，执行效率和空间使用都比较差。事实也证明了这一点，这是 leetcode.com 对我的算法给出的评价：

Runtime: 819 ms, faster than 9.07% of C++ online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 335.7 MB, less than 5.39% of C++ online submissions for Longest Substring Without Repeating Characters.

运行时间只超过了 9% 的 C++ 实现方案，而内存使用只比 5% 的 C++ 方案节省内存！
接下来易水尝试优化算法，当时闪过一个想法，所谓的“最长不重复子串”，可以定义为两个重复字符之间的最大长度，但易水在把这个想法转换为算法时遇到了障碍，始终无法摆脱字符查找、比较的思维定势，因此一直找不到更优解决方案。直到在评论区看到stanislav-iablokov的解法，才惊叹于他的实现方案之简洁优雅，我将在下一篇介绍他的解决方案，这一方案所采用的思路，正是易水上面提到的想法！