无重复字符的最长子串
题目
给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
请注意,你的答案必须是 子串 的长度,”pwke” 是一个子序列,不是子串。
思路
遍历整个字符串,将字符转换成整数进行对比
???
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| #define MAX(a, b) ((a) > (b) ? (a) : (b))
int lengthOfLongestSubstring(char* s) { int len = 0; int i = 0; int left = 0; int m[256] = {0};
for(i = 0; i < strlen(s); ++i) { if(m[s[i]] == 0 || m[s[i]] < left) { len = MAX(len, i - left + 1);
} else { left = m[s[i]]; }
m[s[i]] = i + 1;
}
return len; }
|
LeetCode运行测试时间8ms
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 34 35 36 37
| int lengthOfLongestSubstring_8ms(char* s) { int maxlen = 0, currlen = 0; int table[128], i, j, start = 0; memset(table, 0, sizeof(table));
for(i = 0; s[i] != '\0'; ++i) { int num = ++table[s[i]];
if(num == 2) { if(currlen > maxlen) { maxlen = currlen; }
for(j = start; j < i; ++j) { if(s[j] == s[i]) { table[s[j]] = 1; start = j + 1; break;
} else { --currlen; table[s[j]] = 0; } }
} else { ++currlen; } }
if(currlen > maxlen) { maxlen = currlen; }
return maxlen; }
|