今天在leetcode做到一道题，题目本身比较简单，但是用到了二分思想，感觉蛮有意思，记录一下。

题目描述

题目名称：无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度
示例 1:

  1. 输入: s = "abcabcbb"
  2. 输出: 3 
  3. 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

  1. 输入: s = "bbbbb"
  2. 输出: 1
  3. 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

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

提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

暴力算法

如下图所示，依次设置一个长度为1、2、…、n的滑动窗口，如果存在一个长度为k的滑动窗口包含的字符串不重复，那么无重复字符的最长子串长度大于等于k， 时间复杂度为二分思想 - 图1。
image.png

利用二分思想优化暴力算法

假设有一个check(string &s,int l)用于判断字符串s是否存在长度为l的子串，满足不含重复字符串，暴力算法是依次判断check(s,1),check(s,2),…,check(s,n)；而二分是先判断check(s,(1+n+1)/2)，再根据结果继续二分查找，代码如下所示。

  1. int lengthOfLongestSubstring(string s) {
  2.     if(s.size()==0) return 0;
  3.     int low=1,high=s.size(),mid;
  4.     while(low<high){
  5.         mid=(low+high+1)/2; //注意这里不是（low+high)/2,目的避免low=mid跳不出循环
  6.         if(check(s,mid)) low=mid;
  7.         else high=mid-1;
  8.     }
  9.     return low;
  10. }

再补充一下check函数

  1. bool check(string &s,int l){
  2.     int cnt[256]={0},k=0;
  3.     for(int i=0;s[i];i++){
  4.         if(cnt[s[i]]==0) k++;
  5.         cnt[s[i]]++;
  6.         if(i>=l){
  7.             cnt[s[i-l]]--;
  8.             if(cnt[s[i-l]]==0) k--;
  9.         }
  10.         if(k==l) return true;
  11.     }
  12.     return false;
  13. }

时间复杂度二分思想 - 图3