C++ leetcode Longest Substring Without Repeating Characters

要开学了，不开森。键盘声音有点大，担心会吵到舍友。今年要当个可爱的技术宅呀~

题目：Given a string, find the length of the longest substring without repeating characters.

Examples: Given "abcabcbb", the answer is "abc", which the length is 3.

第一反应的解法，直接贴代码吧，38ms的运行时间，击败58%。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        string result("");  //用来存储目前没有重复的子串
        int tmp = 0;      //没有重复字母子串的最大长度
        int now = 0;
        for(int i = 0; i != s.size(); i++){
            int pos = -1;
            if ( (pos = result.find(s[i]) )== -1)   
                result = result + s[i];
                
            else{
                tmp = result.size()>tmp?result.size():tmp;
                result = (pos+1==result.size()?"":result.substr(pos+1)) + s[i]; 
            }
        }
        return result.size()>tmp?result.size():tmp;
    }
};

　　很简单的解法，我却写了蛮久的，因为对string不熟悉，而且没考虑越界，学到了两个string的成员函数，一个是find（），另一个是截取子串的函数substr（）。自己最智障的地方就是截取子串的时候索引写错了竟然一直都没反应过来，哎，脑子真是个好东西啊。

　　速度很慢，想把字符串转成hash函数做，但是没想好具体的解法。看一眼大神的，6ms的，有想法了。OK~23ms,击败了65%，下面这个代码和原来的代码算法相似，都是用滑动窗口的做法，但是下面这个解法将find（）函数改成了用hash表实现，节省了遍历原串时在子串中查找有没有这个字母的时间，而且将找到现在情况下的最长子串不赋值给一个新的string，只用指针start标注该子串在原串中的起始位置，节省了赋值时间。不过更新start值时，直接将该字母出现的前一个位置+1赋给了start，没有考虑现在子串的起始位置，照这个bug找了好久，脑子啊，我什么时候才能有啊！哭唧唧！但是明明和大神解法一样，怎么测试时间差这么多？喵喵喵？

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
    int flag[256];
    int start = 0;
    int longest = 0;
    for (int i = 0; i <256; i++)
        flag[i] = -1;
    int i;
    for(i = 0; i< s.size(); i++){
        if (flag[s[i]] != -1)                    
            start = (flag[s[i]] + 1)>start?flag[s[i]]+1:start;    
        longest = longest >= (i-start+1)?longest:(i-start+1);
        flag[s[i]] = i;
    }
    return longest;
    }
};

　　好啦，水完了今天的博客和LeetCode~找饭吃~

C++ leetcode Longest Substring Without Repeating Characters

相关推荐