题解 | 最长不含重复字符的子字符串

#include <unordered_map>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    int lengthOfLongestSubstring(string s) {
        // write code here
        if(s.length()==0) return 0;
        //每个字母所在的位置，开始的位置，要换开始位置的时候才比较当前串和已经得到的最长串。
        int pos = 1, res = 0;
        unordered_map<char, int> ump;
        //string ans="";
        //string可以更改内容，不是const， char[] 固定了就不能改了，退化成指
        for (int i = 0; i < s.size(); ++i) {
            
            if (ump[s[i]] >= pos) {
                //发现重复的，如果没有改变就没有初始值
                res = max(res, (i + 1 - pos));
                pos = ump[s[i]]+1;//新pos
            }
            ump[s[i]] = i + 1;
        }
        int len = s.size();
        res = max(res, (len-pos+1));
        return res;
    }
};

对于这道题的直观感受就是要找到地址，然后通过是否上个地址在此次区间内来判定是否到下一个区间去。

所以我需要上个地址，和此区间的一个范围。

上个地址只有一个所以可以直接使用hash来存储，区间范围头部需要标定，在发生矛盾是转换，而尾部就是我们现在已经走到的坐标。

这里有两个问题，一个是转换条件，前面已经说了；一个是到尾部之后可能是最长的那一串但是没有记录了，所以要单独处理。

空间复杂度为O(1)，时间复杂度为O(n)。

#include <unordered_map>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    int lengthOfLongestSubstring(string s) {
        // write code here
        if(s.length()==0) return 0;
        int res = 0;
        unordered_map<char, int> mp;
        int len = s.length();
        vector<int> dp(len+1, 0);//int dp[len+1]; // 运行时确定长度，不被C++标准支持
        for(int i = 1; i <= s.length(); ++i){
            if(mp.count(s[i-1])==0){
                dp[i] = dp[i-1]+1;
            }
            else{
                dp[i] = min(dp[i-1]+1, i - mp[s[i-1]]);
            }
            mp[s[i-1]] = i;
            res = max(res, dp[i]);
        }
        return res;
    }
};

在思考这个问题的时候我并没有考虑到动态规划的做法，因为更小的部分很容易想到只是少一个的字符串，而上一个位置和它没有关系，那么这个转换其实并不方便。

但是官方题解给了一个很巧妙的东西，就是直接比较它和上一个直接加一的谁更短，因为如果上一个的范围不包括目前这个值的上一位，那么上一个范围+1就会比目前到上一个相同值的位置的距离更短。

这个代码我第一次写的时候用了int数组，想着运行时出结果可能过不了编译，结果居然过了（感觉是编译器原因，如GCC和Clang支持C99的变长数组作为编译器扩展。尽管这并不是C++标准的一部分）。

但是还是建议使用vector存储变长的数组，万一哪天碰到一个编译器启用了严格的C++标准模式呢。