无重复字符的最长子串

问题描述：
给定一个字符串，找出不含有重复字符的 最长子串 的长度。

示例：

给定 “abcabcbb” ，没有重复字符的最长子串是 “abc” ，那么长度就是3。

给定 “bbbbb” ，最长的子串就是 “b” ，长度是1。

给定 “pwwkew” ，最长子串是 “wke” ，长度是3。请注意答案必须是一个子串，”pwke” 是 子序列 而不是子串。

分析：
①必须会的暴力破解法，求无重复字符的最长子串，只需要把所有的子串列出来，找到其中最长的无重复子串即可。
比如对于长度为5的字符串abcda, 我们可以先看看abcda是否为最长无重复字符子串，遍历1遍，if(arr.indexOf(item) !== i) { 说明有重复字符}
再看看长度为4的子串，abcd、bcda…
…
该法缺点：效率极低，运行时间长。
n*n +(n-1)*(n-1)+…+2*2+1*1
O(n^3)
②动态规划法，c[i][j]表示从i到j的串的最长无重复子串
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-C3n5yrVK-1639311705103)(//img-blog.csdn.net/20180321171900738?watermark/2/text/Ly9ibG9nLmNzZG4ubmV0L1RyYWN5X2Zyb2c=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70)]
如果s[j]不在从i到j-1的子串中，c[i][j]=c[i][j-1]+1；反之，c[i][j]=0
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gac3RWgD-1639311705106)(//img-blog.csdn.net/20180321172154735?watermark/2/text/Ly9ibG9nLmNzZG4ubmV0L1RyYWN5X2Zyb2c=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70)]
观察上表，可以看出，对角线值一定为1（分析略），每一行可以从对角线处开始遍历，遇到0结束该行遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

var x=new Array();
  	var len=s.length;
  	var max=0;
  	var sub="";
  	for(let i=0;i<len;i++)
  	{
  		x[i]=new Array();
  	}
  	for(let i=0;i<len;i++)
  	{
  		sub=s[i];
  		for(let j=i;j<len;j++)
  		{
  			if(i==j)
  			{
  				x[i][j]=1;
  			}
  			else
  			{
  				if(sub.indexOf(s[j])==-1)
  				{
  					x[i][j]=x[i][j-1]+1;
  				}
  				else
  				{
  					break;
  				}
  			}
  			max=x[i][j]>max?x[i][j]:max;
  			sub+=s[j];
  		}
  	}
  	return max;

缺点：效率依旧很低。双重循环，时间复杂度O(n^2)
③尺取法
网上看了代码，知道了有尺取法这个东西。
步骤：

• 初始化两个指针（head,tail）指向字符串开头

• tail++,如果tail指针指向的字符不与head和tail-1之间的字符重复，tail继续向后移动，更新max；反之，head一直加到没有重复字符为止

• 重复第二步骤，直到tail指针指向字符串结尾

  代码：

1
2
3
4
5
6
7
8

const map = {};
   var left = 0;
   
   return s.split('').reduce((max, v, i) => {
       left = map[v] >= left ? map[v] + 1 : left;
       map[v] = i;
       return Math.max(max, i - left + 1);
   }, 0);

这串简短的代码就像女神一样优雅美丽。
（这段js涉及split函数、reduce函数、箭头函数等内容，请自行了解）

翻译成大白话就是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

const map={};
   var left=0;
   var max=0;
   var left=0;
   for(var i=0;i<s.length;i++)
   {
   	var v=s[i];
   	if(map[v]>=left)//一开始map[v]不存在，undefined，式子值为false
   	{
   		left=map[v]+1;
   	}
   	map[v]=i;
   	if(max<i-left+1)
   	{
   		max=i-left+1;
   	}
   }
   return max;

说一下对尺取法的理解吧
目标：最长的无重复子串
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8H6yZiqj-1639311705110)(//img-blog.csdn.net/20180321185401942?watermark/2/text/Ly9ibG9nLmNzZG4ubmV0L1RyYWN5X2Zyb2c=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70)]
当出现上述情况时候，在当前子串范围内max=6，该子串的子串max一定小于6
接下来无论head向右如何移动（head<=tail），所能得到的子串（如cdabsa、dabsa）的最大无重复字符长度len一定是小于6的，故对它们进行计算是没有意义的，该部分的max已经找到，直接将head指针移到b字符处，计算下部分的max
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SPuDhSu2-1639311705112)(//img-blog.csdn.net/20180321190148533?watermark/2/text/Ly9ibG9nLmNzZG4ubmV0L1RyYWN5X2Zyb2c=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70)]
时间复杂度： 只遍历一遍，O(n)