首页 > 代码库 > 【编程】leetcode_longest substring without repeating characters
【编程】leetcode_longest substring without repeating characters
class Solution {public: int lengthOfLongestSubstring(string s) { char cHash[256]; int cnt = 0, maxCnt = 0; int i, j, k, sSz = s.size(); char chRep; memset(cHash, 0, 256); cnt = 1; // initialization for(i = 0, cHash[0] = 0; i < sSz; ) { cHash[s[i]] = 1; for (j = i + 1; j < sSz; j++) { if (cHash[s[j]] == 0) { cnt++; // increase length cHash[s[j]] = 1; } else { chRep = s[j]; break; // got the same character } } if (cnt > maxCnt) // renew the maxcnt { maxCnt = cnt; } // got the next i index, find where is the chSame for (k = j - cnt; k < j; k++) { if (s[k] == chRep) { break; } cnt--; // decrease cHash[s[k]] = 0; // delete from hashtable } i = j; // i start from the j position } return maxCnt; }};
思路：
1. 使用char cHash[256]作为hash表来存储某个字符是否已经出现过；
2. 遍历字符串，出现的字符串在hash表中置1；
3. 一旦发现重复出现的字符串，返回当前子串查找，当前子串中在出现字符之前的字符从hash表中删除；
4. 下次循环可以接着子循环的位置继续下去，看上去是两层循环，其实对于整个字符串只会遍历一次。
【编程】leetcode_longest substring without repeating characters
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。