Day11-字符串-无重复字符最长子串
一 唠唠嗑
周末回了趟家，参加高中好哥们的婚礼来着，时间真是快呀
什么，你问我为什么周末没更？
二 来吧
Q：已知一个字符串，求用该字符串的无重复字符的最长子串（有的要求求长度，今天直接求子串）
这时候你脱口而出：这还不简单，把一个字符串的所有可能结果全列出来，然后根据无重复字符这个条件过滤呗
但其实我们说出来的时候，就知道这肯定不是面试官要的答案，毕竟N^2的时间复杂度
那我们怎么优化呢？
是不是不用列出所有的子串？因为一旦出现重复字符，后面的枚举都没有意义了？
我们可以这样处理逻辑：
1.建立字符哈希char_map，来保存字符数量
2.建立一个，当前满足条件的最长子串，即字符串word
3.建立，遍历到当前字符时，最长的子串，即字符串result，最终返回的就是result
4.建立两个指针（i和begin）都指向字符串第一个字符
5.i指针从头向后遍历字符串，用char_map记录字符数量
如果word中，没出现过该字符：
对word尾部添加该字符，并检查result是否需要更新
如果word中，出现了该字符：
将begin指针向后移动，更新char_map中字符数量，直至当前重复的字符数量重新变回1，更新word，将word赋值为begin与i之间的子串
即，我们维护一个滑动窗口，窗口左边界是begin，右边界是i，向后滑动，遍历一遍字符串，即O（N）时间复杂度。
举例：
对于string = “abcbadab”
1. i -> a
begin -> a
word = "a"
2.i -> b
begin ->a
word = "ab"
3.i -> c
begin -> a
word = "abc"
4.i -> b,此时char_map[b] = 2，于是begin向后移动，直到移动到c，此时char_map[b] = 1, 此时word = “cb”，以此类推。
三 完整代码及注释
//
// Created by renyi on 2019/6/17.
//
#include <iostream>
#include <string>
using namespace std;
string longestSubString(string s){
int begin = 0;//窗口的头指针，即窗口左边界
string word = "";//记录当前满足条件的最长子串
string result = "";//记录结果
int char_map[128] = {0};//记录字符数量的字符哈希
for (int i = 0; i < s.length(); i++) {
char_map[s[i]]++;
if (char_map[s[i]] == 1){//word中没出现过该字符
word += s[i];//把当前字符添加进word
if (result.length() < word.length()){
result = word;//如果word长度超过了当前result长度，则重新赋值result
}
} else{//当word中重复出现了该字符
while (begin < i && char_map[s[i]] > 1){
char_map[s[begin]]--;//当该字符的字符哈希值，即数量大于1的时候，将begin持续向右移动，知道begin与i维护的滑动窗口中，该字符数量为1
begin++;
}
word = "";
for (int j = begin; j <= i; j++) {
word += s[j];//重置word为begin与i维护的滑动窗口之间的字符串，此时word内不包含重复字符，继续向后遍历
}
}
}
return result;
}
int main(){
string string1 = "abcdabcabbcdefgaaaaaaa";
string result = longestSubString(string1);
cout << result << endl;
return 0;
}运行结果
修改字符串为
string string1 = "abcdabcabcdefgaaa";此时再次运行，结果为
