mardi 8 mai 2018

Leetcode--3 find the longest substring without repeating character

The target is simple--find the longest substring without repeating characters,here is the code:

 class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0;
        int dic[256];
        memset(dic, -1, sizeof(dic));
        int len = s.size();
        int idx = -1;

        for (int i = 0;i < len;i++) {
            char c = s[i];
            if (dic[c] > idx)
                idx = dic[c];

            ans = max(ans, i - idx);

            dic[c] = i;
        }
        return ans;
    }

};

From its concise expression,I think this is a high-performance method,and we can get that its Time Complexity is just O(n).But I'm confused about this method,though I came up with some examples to understand,can anyone give some tips or idea to me?

Aucun commentaire:

Enregistrer un commentaire