哈希+滑动窗口

• 是否重复->哈希，最长->双指针计算长度
• 当出现重复时，子字符串的从上一个字符的下一位开始计算长度，用哈希保留字符和上一次出现的索引
• 注意最后字符不重复时计算长度为end-start+1,最后字符重复时字符长度为end-start

#include <unordered_map>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    int lengthOfLongestSubstring(string s) {
        // write code here

        int max_length = 0, length = 0;
        int start = 0, end = 0;
        unordered_map<char, int> ump;
        for (int i = 0; i < s.size(); i++) {
            if (ump.find(s[i]) == ump.end()
                    || ump[s[i]] == -1) {
                //不存在
                ump[s[i]] = i;
                end = i;
                if(i==s.size()-1)
                {
                    if(max_length<end-start+1)
                    {
                        max_length=end-start+1;
                    }
                }
            } else {
                //存在
                //计算长度
                end = i;
                length = end - start;
                if (max_length < length) {
                    max_length = length;
                }
                int j = ump[s[i]]; //前面的索引
                for (int k = start; k <= j; k++) {
                    ump[s[k]] = -1;
                }
                start = j + 1;

                ump[s[i]] = i;

            }

        }
        return max_length;
    }
};

更简洁的写法

• 创建mp[i]的初始值是0
• 每个数统一处理先加1再判断是否重复
• 巧妙的遍历直到重复元素

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> mp; 
        int res = 0;
        for(int left = 0, right = 0; right < s.length(); right++){ 
            mp[s[right]]++; 
            while(mp[s[right]] > 1) 
                mp[s[left++]]--; 
            res = max(res, right - left + 1); 
        }
        return res;
    }
};

哈希+动态规划

• 本质是一样的
• 区别在于1.dp保存结果 2. 最大值的计算，滑动窗口是移动一格知道符合条件，这里是直接保存索引

class Solution {
  public:
    int lengthOfLongestSubstring(string s) {
        //哈希表记录窗口内非重复的字符及其下标
        unordered_map<char, int> mp;
        int res = 0;
        //dp[i]表示以下标i结尾的字符串最长不含重复子串的长度
        vector<int> dp = vector<int>(s.length() + 1, 0);
        for (int i = 1; i <= s.length(); i++) {
            //哈希表中没有，说明不重复
            if (mp.find(s[i - 1]) == mp.end())
                //前一个加1
                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;
    }
};