首页 > 代码库 > Leetcode--lengthOfLongestSubstring

Leetcode--lengthOfLongestSubstring

2024-08-19 09:46:23   220人阅读

这道题很简单，我的思路是设置一个数组储存字符，然后设置两个浮标，右浮标不断向后移动，如果浮标所在字符在数组中有出现，就存储长度，然后把左字符的位置设置为出现重复字符的后一个位置，然后存储长度，清空数组，接着不断重复即可。

主要要解决的是检测重复数组所费时间，如果单纯使用数组，时间复杂度就是O（n2），可以使用hash表储存字符，可以降低时间复杂度为O(n)

    static int lengthOfLongestSubstring(std::string s) {
        if (s.length() == 0)
            return 0;
        int length = 1, length_2 = 0, record = 0;
        map<char, int> temp;
        for (int i = 0; i < s.length(); i++) {
            if (temp.count(s[i]) != 0) {
                if (i - temp[s[i]] + 1 > length_2)
                    length_2 = length;
                temp.clear();
                i += temp[s[i]];
                length = 0;
                continue;
            }
            temp[s[i]] = i;
            ++length;
        }
        if (length > length_2)
            length_2 = length;
        return length_2;
    }
};

还有Leetcode上提供了一个很好的解法，分享下

static int lengthOfLongestSubstring(string s) {
        int n = s.length();
        int i = 0, j = 0;
        int maxLen = 0;
        bool exist[256] = {false};
        while (j < n) {
            if (exist[s[j]]) {
                maxLen = max(maxLen, j - i);
                while (s[i] != s[j]) {
                    exist[s[i]] = false;
                    i++;
                }
                i++;
                j++;
            } else {
                exist[s[j]] = true;
                j++;
            }
        }
        maxLen = max(maxLen, n - i);
        return maxLen;
    }

这个解法真的太巧妙了，设置左右两个浮标，然后设置一个大小为256的bool数组，对应256个ascii码。

妙处就是i和j都只把这个string从开始到结束遍历了一遍。

本来写了很长的讲解 ，但是觉得说的太繁琐了，实在是不太擅长向别人讲知识。脑袋里面能模拟运行，但是就是讲不出来，具体的大家可以运行单步调试一下，就可以体会到其中妙处

 

Leetcode--lengthOfLongestSubstring


联系
我们