Longest Substring Without Repeat

image.png

题目

Given a string, find the length of the longest substring without repeating characters.

分析 类似道理

滑动窗口协议：

TCP将独立的字节数据当作流来处理。
一次发送一个字节并接收一次确认显然是不可行的。即使重叠传输（即不等待确认就发送下一个数据），速度也还是会非常缓慢

如果我们在任一时间点对于这一过程做一个“快照”，那么我们可以将TCP buffer中的数据分为以下四类，并把它们看作一个时间轴：

1. 已发送已确认 数据流中最早的字节已经发送并得到确认。这些数据是站在发送设备的角度来看的。如下图所示，31个字节已经发送并确认。

2. 已发送但尚未确认 已发送但尚未得到确认的字节。发送方在确认之前，不认为这些数据已经被处理。下图所示14字节为第2类。

3. 未发送而接收方已Ready 设备尚未将数据发出，但接收方根据最近一次关于发送方一次要发送多少字节确认自己有足够空间。发送方会立即尝试发送。如图，第3类有6字节。

4. 未发送而接收方Not Ready 由于接收方not ready，还不允许将这部分数据发出。

image003.jpg

接收方采用类似的机制来区分已接收并已确认，尚未接受但准备好接收，以及尚未接收并尚未准备好接收的数据。实际上，收发双方各自维护一套独立的变量，来监控发送和接收的数据流落在哪一类。

丢包情况

image.png

• 只有发送没有ack

  
  image.png

如果我们这个Ack始终不来怎么办呢？
发生的情况：一直在等Ack。如果一直等不到的话，我们也会把读进缓存的待发送的包也一起发过去。但是，这个时候我们的窗口已经发满了。所以并不能把12号包读进来，而是始终在等待5号包的Ack。

超时重发

这时候我们有个解决方法：超时重传 这里有一点要说明：这个Ack是要按顺序的。必须要等到5的Ack收到，才会把6-11的Ack发送过去。这样就保证了滑动窗口的一个顺序。

image.png

这时候可以看出5号包已经接受到Ack，后面的6、7、8号包也已经发送过去已Ack。窗口便继续向后移动。

代码

#include <iostream>
#include <vector>
using namespace std;

/**
https://leetcode.com/problems/longest-substring-without-repeating-characters/
Given a string, find the length of the longest substring without repeating characters.

 */
class Solution {
public:
    int lengthOfLongestSubstring(string s)
     {
         vector<int> hash_map(256,-1);

         int out=0;
         int start=0;
         int end=0；

      for (int end=0;end<s.size();end++)
         {  
           //contain
           if (hash_map[s[end]] != -1)
           {
               start=max(start,hash_map[s[end]]+1);//重复元素不计算，修改start位置 
           }    
           out=max(out,end-start+1);//每次都计算一次
           hash_map[s[end]]=end;
         }
         return out;
    }
};


int   main(int   argc, char*   argv[])
{
    Solution test;
    cout<<"abcabcbb = "<<test.lengthOfLongestSubstring("abcabcbb")<<endl;
    cout<<"bbbbb = "<<test.lengthOfLongestSubstring("bbbbb")<<endl;

    
    return   0;
}
//Longest Substring with At Most Two Distinct Characters