leetcode-3

leetcode 3

// 将每个子串放入set 然后计算最大长度
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.length() < 1) return 0;
        int len = s.length();
        int ans = 0;
        for(int i = 0;i < len; ++i) {
            for(int j = i + 1;j <= len; ++j) {
                if(all_unique(s, i, j)) ans = ans > j - i ? ans : j - i;
            }
        }
        return ans;
    }
    bool all_unique(string s, int start, int end) {
        set<char> c;
        for(int i = start;i < end; ++i) {
            if(c.find(s[i]) != c.end()) {
                return false;
            }
            c.insert(s[i]);
        }
        return true;
    }
};
// 哈希表
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        set<char> hash_set;
        int ans = 0, i = 0, j = 0, n = s.size();
        while(i < n && j < n) {
            if(hash_set.find(s[j]) == hash_set.end()) {
                ans = ans > (j - i + 1) ? ans : (j - i + 1);
                hash_set.insert(s[j]);
                j++;
            }
            else {
                hash_set.erase(s[i]);
                i++;
            }
        }
        return ans;
    }
};
//map
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char, int> m;
        int i = 0, j = 0, ans = 0, n = s.size();
        for(; j < n; ++j) {
            if(m.find(s[j]) != m.end())
                i = max(m[s[j]], i);
            ans = max(ans, j - i + 1);
            //m.insert({s[j], (j + 1)});
            m[s[j]] = j + 1;
        }
        return ans;
    }
};
// 映射数组
/*
int [26] 用于字母 ‘a’ - ‘z’ 或 ‘A’ - ‘Z’
int [128] 用于ASCII码
int [256] 用于扩展ASCII码
*/
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int map_arr[128] = {0};
        int i = 0, j = 0, ans = 0, n = s.size();
        for(; j < n; ++j) {
            i = max(map_arr[s[j]], i);
            ans = max(ans, j - i + 1);
            map_arr[s[j]] = j + 1;
        }
        return ans;
    }
};