题目： 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:

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

示例 2:

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

示例 3:

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

思路：

dp数组的含义：以第i个字符结尾的不含重复字符的子字符的最大长度
1.如果当前字符首次出现，那么dp[i] = dp[i - 1] + 1
2.如果当前字符和哈希表中记录的发生重复，计算当前字符位置与前边重复的字符位置的距离，这里分为两种情况
（1）i - umap[s[i]] > dp[i - 1]如果当前的位置减去上次的位置大于dp[i - 1]，说明重复的字符已经不在之前的子串了，
因此dp[i] = dp[i - 1] + 1
（2）i - umap[s[i]] <= dp[i - 1]如果小于等于，说明还在当前的dp[i - 1]子串中，则dp[i] = i - umap[i];
3.更新一下哈希表
4.取出最大的长度。

class Solution {
public:int lengthsubstr(string s) {if (s.size() == 0 || s.size() == 1)return s.size();unordered_map<char, int> umap;vector<int> dp(s.size(), 0);int max_value = 0;dp[0] = 1;umap[s[0]] = 0;for (int i = 1; i < s.size(); i++) {//没记录过上一个位置，说明第一次出现 肯定可以连接dp[i-1]if (umap.find(s[i]) == umap.end()) {dp[i] = dp[i - 1] + 1;}//记录过上一个位置。它有两种可能（1）在dp[i-1]的范围外。（2）在dp[i-1]里面else {if (i - umap[s[i]] > dp[i - 1]) {//上一个位置不在dp[i-1]范围内 ，可以直接连起来dp[i] = dp[i - 1] + 1;}else {//上一个位置在dp[i-1]范围内 ，则长度 = 这个位置-上一个位置dp[i] = i - umap[s[i]];}}umap[s[i]] = i;max_value = max(max_value, dp[i]);}return max_value;}
};int main() {string s = "abcabcbb";Solution ss;cout << ss.lengthsubstr(s) << endl;return 0;
}