LeetCode题集-3 - 无重复字符的最长子串

题目：给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

我们先来好好理解题目，示例1中怎么得到长度为3的？

如果以第一个字符a为起始，不含重复的最长子串是abc；则我们这样表示(a)bcabcbb -> (abc)abcbb，如此表达枚举出所有可能的情况如下：

1.(a)bcabcbb -> (abc)abcbb；

2.a(b)cabcbb -> a(bca)bcbb；

3.ab(c)abcbb -> ab(cab)cbb；

4.abc(a)bcbb -> abc(abc)bb；

5.abca(b)cbb -> abca(bc)bb；

6.abcab(c)bb -> abcab(cb)b；

7.abcabc(b)b -> abcabc(b)b；

8.abcabcb(b) -> abcabcb(b);

在所有可能的情况中满足条件的最长的子串分别为abc、bca、cab三个，三个长度都是3，因此示例1的结果为3。

解法一、双指针法

通过上面枚举出的所有情况，可以发现满足要求的字串是从起始位置向结束位置滚动的，并且在这个过程中，字串的长度也是在变化的，那也就是说只要我们准备两个指针start和end,并控制好两个指针前进的节奏就可以完成任务。

那如何控制指针节奏呢？

首先说第二个指针end，我们把上面1.(a)bcabcbb -> (abc)abcbb中步骤进行补充，应该是1.(a)bcabcbb -> (ab)cabcbb -> (abc)abcbb即指针end一步一步往后走，即使遇到重复字符依旧稳步前进。

每当指针end往后移动一位，只需判断这一位有没有在之前的字串中出现过，如果出现过则开始调整指针start。

例如上面的1->2即(abc)abcbb -> a(bca)bcbb过程中，当指针end到第二个a时，而前面的子串abc中已经出现过a了，因此需要把指针start跳转到b即跳转到子串中重复字符后一个位置。

我们用图例详细描述一下从指针end移动到start移动的具体过程。

下面看看具体实现代码。

public static int SlidingWindow(string s)

{

//start指针

var startIndex = 0;

//end指针

var endIndex = 0;

//当前不重复子串长度

var currentLength = 0;

//最长不重复子串长度

var maxLength = 0;

//一直处理直到end指针不小于字符串长度

while (endIndex < s.Length)

{

//获取待处理字符

var pendingChar = s[endIndex];

//判断待处理字符串是否在当前子串中存在

for (var i = startIndex; i < endIndex; i++)

{

//如果子串中已经存在待处理字符

if (pendingChar == s[i])

{

//把start指针跳转至子串中重复字符下一个位置

startIndex = i + 1;

//重新计算当前不重复子串长度

currentLength = endIndex - startIndex;

break;

}

}

//end指针向后移动一位

endIndex++;

//当前不重复子串长度加1

currentLength++;

//比较并更新最大不重复子串长度

if (currentLength > maxLength)

{

maxLength = currentLength;

}

}

return maxLength;

}

分析可知，因为是双层循环while+for所以算法时间复杂度是：O(N2)，又因为没有引用额外的空间因此空间复杂度是：O(1)。

解法二、双指针+哈希法

对于双层循环我们还是有办法进行优化的，最常见的做法是空间换时间，即把内层循环通过哈希表替换换掉，这样通过哈希表提供O(1)查询时间复杂度，使得整个算法时间复杂度达到O(N)。但是哈希表需要额外的O(N)空间

如果用哈希表存储已经存在字符，应该如何存储呢？key存什么？value存什么？这里有一个问题是哈希表只存当前子串的字符？还是存所有已存在字符？如果只存当前子串的字符意味着每次都要清除哈希表，而且清除动作时间复杂度是O(N)。所以我们选择存所有已存在字符。

如果存所有已存在字符，则要注意判断无效数据，比如abc(ba)b中我们不能把最后一个b和第一个b比较，因为当前子串是(ba)，所以应该和第二个b做判断。

实现代码如下：

public static int SlidingWindowDictionary(string s)

{

//start指针

var startIndex = 0;

//end指针

var endIndex = 0;

//当前不重复子串长度

var currentLength = 0;

//最长不重复子串长度

var maxLength = 0;

//字典表，存储已存在字符

var dic = new Dictionary();

//一直处理直到end指针不小于字符串长度

while (endIndex < s.Length)

{

//获取待处理字符

var pendingChar = s[endIndex];

//判断待处理字符是否在字典表中存在，并且其索引位置在当前子串中

if (dic.TryGetValue(pendingChar, out var value) && value >= startIndex)

{

//把start指针跳转至子串中重复字符下一个位置

startIndex = value + 1;

//重新计算当前不重复子串长度

currentLength = endIndex - startIndex;

}

//更新字典表已存在字符最后的索引位置

dic[pendingChar] = endIndex;

//end指针向后移动一位

endIndex++;

//当前不重复子串长度加1

currentLength++;

//比较并更新最大不重复子串长度

if (currentLength > maxLength)

{

maxLength = currentLength;

}

}

return maxLength;

}

解法三、双指针+数组法

那这个算法还有优化空间吗？我们知道哈希表操作是有消耗的，有没有比哈希表更好的存储方式呢？

针对不同的问题可能有不同的方式，对于这一题，的确有点特别，不知道有没有注意到题目最下面的“s 由英文字母、数字、符号和空格组成”描述，这不由的让我想到ASCII码表。

如果是s是由ASCII码表里的字符组成，那么就代表每一个字符都有一个对应的十进制值，这就是天然的下标，然后以所有的ASCII码表数量构建一个字符数组用来存放已经存在的字符，而每个字符存放位置就是其对应的十进制值，这样不就可以解决存储的问题了吗？

因为我们先构建了数组，因此还需要给数组每个元素赋值为-1，用来标记当前元素还没有使用。

具体实现代码如下：

public static int SlidingWindowArray(string s)

{

//start指针

var startIndex = 0;

//end指针

var endIndex = 0;

//当前不重复子串长度

var currentLength = 0;

//最长不重复子串长度

var maxLength = 0;

//定义可能存在的字符数组，并全部填充为-1

var arr = new int[128];

Array.Fill(arr, -1);

//一直处理直到end指针不小于字符串长度

while (endIndex < s.Length)

{

//获取待处理字符

var pendingChar = s[endIndex];

//判断待处理字符索引位置是否在当前子串内

if (arr[pendingChar] >= startIndex)

{

//把start指针跳转至子串中重复字符下一个位置

startIndex = arr[pendingChar] + 1;

//重新计算当前不重复子串长度

currentLength = endIndex - startIndex;

}

//更新数组中已存在字符最后的索引位置

arr[pendingChar] = endIndex;

//end指针向后移动一位

endIndex++;

//当前不重复子串长度加1

currentLength++;

//比较并更新最大不重复子串长度

if (currentLength > maxLength)

{

maxLength = currentLength;

}

}

return maxLength;

}

虽然已经实现了三种解题方法，但是到底性能如何？下面我们对三个方法进行一组基准测试，每个方法测试10000次，每次随机构建一个长度为10000的字符串。

可以发现双指针+哈希表比单纯的双指针性能还有差很多，而双指针+数组整体表现就好很多了。由此可见双指针+哈希表还是有其局限性的，虽然理论值很好，但是实际表现不尽如人意，这也提醒我们要在合适的地方使用合适的方法，才能更好的解决问题。

注：测试方法代码以及示例源码都已经上传至代码库，有兴趣的可以看看。https://gitee.com/hugogoos/Planner