无重复字符的最长子串问题
无重复字符的最长子串问题
一·题目简述：
leetcode题目链接：. - 力扣（LeetCode）
二·思路汇总：
遇到这道题，当看到重复也就不难想到哈希表了吧，遇到子串让我们联想到可以用滑动窗口来控制其移动。故这道题就可以用哈希+滑动窗口解决。
下面分别用c和c++解答，这两种语言对应的思路均一样。
对于这道题仔细讲一下c++做法，c的思路也会提一下。
2·1c语言解法：
思路（应用滑动窗口和简单哈希表）；
滑动窗口：左右两个指针，右边走一个，判断对应的值与窗口内的是否有重复，没有直接把其纳入窗口
否则就是有重复，左指针走到重复的位置+1，相当于把重复的值排出窗口，然后缩小窗口，
整个窗口依次右移直到走到数组末端。（也可以用左右指针，右套左for循环完成，可以避免本题left左指针多次移动，可以直接给左指针赋位置）
简单哈希表：将原数组对应的值按哈希数组下标存入，方便计算数组内原值出现次数。
此题思路：定义好左右指针，然后右指针走，hash数组此下标位置对应数字为0就接着放，否则，动左指针
依次删除放入的数据，直到走到重复的下一个位置，则窗口就无重复数据，接着右指针再动，持续操作，直到右指针越界。
2·2c++解法：
上面说了一大堆，其实总的意思感觉啰嗦了，下面用c++这个解法的思路画图举例说明一下吧！
大概就是这样，整体理解起来不难，有一些优化后原因也在图中说明了。
下面说一下一般滑动窗口的套路：
遇到可以用单向双指针维护的题目就可以这个思路思考，然后根据题意写代码。
c++对本题思路：
滑动窗口+hash表：可以理解为hash内的值即right-left+1；也就是ret，因此只要找到重复字符，也就是说left一定要更新即右移
但是优化掉不可能的结果即left可直接跳到第一个重复数后面的一个，移动完left位置的这个循环即出窗口过程
下面就是更新结果是在出窗口之前更新还是之后更新，这道题选择的是后者，因为如果是之前的话那么反而找到重复的字符，它就会相对真正的大一。
三·解答代码：
3·1c代码：
int lengthOfLongestSubstring(char* s) {
int left=0;
int right=0;//定义左右指针
int slip_win_data_count=0;//记录窗口数据个数大小
int len=strlen(s);
int max=0;
int hash[128]={0};
while(right<=len-1){
if( hash[s[right]]==0){
hash[s[right]]++;
right++;
slip_win_data_count++;
if(slip_win_data_count>=max){
max=slip_win_data_count;//由于每次移动一次右指针放入数据后就记录一下里面的数据个数，及时更新max
}
}
else{
hash[s[left]]--;
left++;
slip_win_data_count--;
}//当右指针出现重复时，左指针不断移动删除hash数组内数据，也会删除不重复的数据直到找到重复数据
//把他删除后指向下一个位置，右边开始移动（更新完窗口，左指针可能移动多次找重复数据）
}
return max;
}3·2c++代码：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n=s.size();
int hash[129]={0};
int ret=0;
for(int left=0,right=0;right<n;right++){
hash[s[right]]++;
while(hash[s[right]]>1){//利用循环完成出窗口操作，移到数组中第一个重复字符后一个位置
hash[s[left++]]--;
}
ret=max(ret,right-left+1);//更新返回值
}
return ret;
}
};腾讯云开发者
