3-Longest Substring Without Repeating Characters @LeetCode
题目
题目中得到的信息有：
一段字符串找出不重复子串的最大长度，只需要长度信息。
思路
肯定是需要将字符串遍历一遍，在遍历过程中就需要查找前面字符串是否出现该字符，因此这是该算法的重点。若没找到，长度加一，若找到了，长度会从前面该字符位置+1处开始算起。下面以图来说明：
假如我们以begin为子串的开始，current表示当前处理的位置。1）当前位置的字符没有出现在[begin,current)的区间内，说明将该值加入到区间内满足没有重复条件，长度加一；
2）若当前值已经在该区间内，加入后肯定会出现重复，则应该将begin移动到没有该值的最左边位置，图中 new begin位置满足该条件。
在移动begin之前首先需要判断[begin, current)是否是现有的最大长度，若是则更新，然后将begin移动到该新位置。
还有一个关键点，就是如何查找当前字符是否出现在[begin, current)区间里，若在从该区间遍历一遍肯定费时间，有没有办法可以一次就能判断出来呢？
对了，可以采用hash的思想，将每个值在字符串的位置放入到以该值为下标的数组中，若数组中保存有值，并且是在[begin,current)范围内，则说明存在。
C算法
int lengthOfLongestSubstring(char* s) {
int tmp[128]; //用于保存字符的下标
int begin = 0, max = 0; //begin和最大长度默认为0
int i, index;
for (i = 0; s[i] != '\0'; i++) { //遍历字符串
if (tmp[s[i]] != 0) { //判断该值是否出现在前面的字符中
index = tmp[s[i]] - 1; //取保存的上一个该值的位置
if (index >= begin) { //判断是否在[begin, current)
if (i - begin > max) //对比是否最大
max = i - begin;
begin = index + 1;//begin新的位置，在前一个该字符的后面，即new begin位置
}
}
tmp[s[i]] = i + 1; //保存该值的最新下标
}
return i - begin > max ? i - begin : max;//最后还需要判断下
}