题目

<>

题意

给出一个字符串，求每个字符都不相同的最长子串长度。

现在题目要求我们求出这两个数的和。

Example 1:

Input: "abcabcbb"Output: 3 Explanation: The answer is "abc", with the length of 3.

思路

错误的思路

二分 + Hash

1、既然要找每个字符都不相同的最长子串长度，那么便可以使用二分思想。首先取中值，假如当前中值是存在每个字符都不相同的子串的，说明应该搜索右边的区间。否则，搜索左边区间。这个二分答案的时间复杂度大概是O(log n)。

2、这里还涉及如何判断是否存在长度为K的不相同子串。我的想法是，拿出每一个子串，然后对每个子串使用Hash思想，对字符出现次数进行统计，若有出现2次的字符，那么说明该子串不成立。若遇到一个全部只出现1次的，那么就终止搜索。这一步的时间复杂度是O(n^2)

很可惜，一共900多个样例，最后一个超时了！

正确的思路

滑动窗口

看了题解，才发现大佬的做法真牛P。他的时间复杂度是O(n)。

大概思路是：维护一个字符串不相同的区间，下面把它称为一个窗口。这个窗口只包含互不相同的连续字符。

具体的做法是：设定该区间的左右区间分别是i，j。然后从左到右遍历字符串，对于每一个新来的字符，先判断该字符是否在区间内出现了。

（1）若出现了，说明区间+新字符形成的新字符串是存在重复字符的。那么不应该将字符加入该区间（窗口不应该向右扩增），而且应该将区间的左边界收缩（窗口左边往右收缩），直到对于新字符来说，区间内不存在重复字符。（该区间要时刻保证，只包含互不相同的连续字符）

（2）若没在区间内出现过，说明当前存在更长的不相同的子串。故将该字符加入区间（窗口向右扩增），并且更新最大值。

正确的代码

该代码是参考题解写的。

class Solution {public:    int lengthOfLongestSubstring(string s) {        int a[256];        int n = s.length();        memset(a, 0, sizeof(int)*256);        int i = 0;//“不相同子串”的左区间        int j = 0;//“不相同子串”的右区间        int ans = 0;        while(i

错误的代码

该代码是辣鸡我写的，有1个样例超时了。

class Solution {//toulanboypublic:    int lengthOfLongestSubstring(string s) {                 long long left = 0;        int right = s.length();        long long a[300];        while(left < right){            int mid = ceil((left + right)/2.0);            bool isExist = false;            //判断是否存在长度为mid的互不相同的子串            for(int i=0; i+mid-1

运行结果

Runtime: 12 ms, faster than 99.84% of C++ online submissions for Longest Substring Without Repeating Characters.Memory Usage: 9.2 MB, less than 99.68% of C++ online submissions for Longest Substring Without Repeating Characters.