大致题意
Longest Substring Without Repeating Characters
就是求最长不含相同符号的子串
解题思路
这题感觉最开始想到的当然是爆爆爆爆爆爆力
感觉暴力太鬼畜了
所以想二分求最大长度
但是还是TLE….
所以说还是很弱智= =！
去网上看了看，发现这题有非常巧妙的解法
解答参考了这篇博客
这篇博客的思路是
就是开一个数组然后记录每个字符上次出现的位置，然后一旦这个字符出现的位置不等于初始值-1，那么就证明这个字符出现过。然后从初始字符串记录值向后移动一位。
但是要注意的是，需要设置一个初始位置记录值_start，当前子串长度就等于 当前位置 i - _start
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int pos[256], _start = -1, len = s.length(),_ans = 0;
memset(pos, -1, sizeof(pos));
for (int i = 0; i < len; i++) {
if (pos[s[i]] > -1) { //该字符出现过
_start = pos[s[i]];
}
_ans = max(_ans, i - _start);
pos[s[i]] = i;
}
return _ans;
}
};
根据如上思路，可以写出这样的代码，但是这样写还是不对，原因在if条件判断，不应该大于-1而是大于_start，因为判断该字符串是否包含在子串是从_start开始，如果从-1开始就是从str[0]开始
