leetcode3/剑指offer48. 无重复字符的最长子串

1.直接哈希法. 复杂度

在扫描完所有的s[0...n]，s[1...n]，s[2...n]....后，最长的极长字符串就是字长不重复子串

#include <iostream>      
#include <string>    
#include <assert.h>

using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
        if (s.empty())
            return 0;

        int visit[256];
         

        int max_length=1;
        int max_index=0;
        for (int i = 0; i < s.size(); i++)
        {   
            memset(visit, 0, sizeof(int)* 256);
            int count = 1;
            visit[s[i]] = 1;
            max_index = i;
            for (int j = i+1; j < s.size(); j++)
            {
                if (visit[s[j]] == 1)
                    break;
                else
                {
                    count++;
                    visit[s[j]] = 1;
                    if (count>max_length)
                    {
                        max_index = i;
                        max_length = count;
                    }

                }
            }
        }
    
        return max_length;
    }
};

string stringToString(string input) {
    assert(input.length() >= 2);
    string result;
    for (int i = 0; i < input.length(); i++) {
        char currentChar = input[i];
        if (input[i] == '\\') {
            char nextChar = input[i + 1];
            switch (nextChar) {
            case '\"': result.push_back('\"'); break;
            case '/': result.push_back('/'); break;
            case '\\': result.push_back('\\'); break;
            case 'b': result.push_back('\b'); break;
            case 'f': result.push_back('\f'); break;
            case 'r': result.push_back('\r'); break;
            case 'n': result.push_back('\n'); break;
            case 't': result.push_back('\t'); break;
            default: break;
            }
            i++;
        }
        else {
            result.push_back(currentChar);
        }
    }
    return result;
}

int main() {
    string line;
    while (getline(cin, line)) {
        string s = stringToString(line);

        int ret = Solution().lengthOfLongestSubstring(s);

        string out = to_string(ret);
        cout << out << endl;
    }
    return 0;
} 

2.滑动窗口

比方说 abcabccc 当你右边扫描到abca的时候你得把第一个a删掉得到bca，然后"窗口"继续向右滑动，每当加到一个新char的时候，左边检查有无重复的char，然后如果没有重复的就正常添加，有重复的话就左边扔掉一部分（从最左到重复char这段扔掉），在这个过程中记录最大窗口长度。

注意以下两点：

• 判断 std 中的 map 中是否有 key
• 存在重复的key,至于为什么取max,考虑出现多个重复的值情形

c++ code:

#include <iostream>      
#include <string>    
#include<algorithm>
#include<map>
#include<math.h>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {

        if (s.empty())
            return 0;
        int max_length=0;
        map<char, int>hashmap;
        int left = 0;
        for (int i = 0; i < s.length(); i++)
        {
            
            if (hashmap.find(s[i]) != hashmap.end())//判断 std 中的 map 中是否有 key
            {
                //left = hashmap[s[i]] + 1;//存在重复的key,至于为什么取max
                 left = max(left,hashmap[s[i]]+1);//存在重复的key,至于为什么取max,考虑出现多个重复的值情形

            }
            max_length = max(max_length, i - left + 1);
            hashmap[s[i]] = i;

        }
         
        return max_length;
    }
};

 

int main() {
    string line="abcabc";
    while (getline(cin, line))
    {
        Solution solu;
        cout<<solu.lengthOfLongestSubstring(line) << endl;
    }
    
    return 0;
}

python code：

#!/usr/bin/env python
#-*- coding:UTF-8 -*-
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        max_len=0
        d={}
        left=0
        for i in range(len(s)):
            if s[i] in d:
                left=max(left,d[s[i]]+1)
            max_len=max(max_len,i-left+1)#注意这里是i不是d[s[i]]
            d[s[i]]= i
 
        return max_len    
            
        
if __name__ == '__main__':
    s="asxasx"
    ret = Solution().lengthOfLongestSubstring(s)
    print(ret)