LeetCode 3. 无重复字符的最长子串

发表于 | 更新于 | 分类于

题意

输出给定子串中最长的子序列的长度。

思路

  • 想法1：直接遍历同时记录这个是否已算在了最大长度内，如果它重复出现了就更新最大值，然后把记录用的变量初始化一下，时间复杂度$O(n)$。但这是错误的，给出个反例abac。

  • 想法2：其实这不就是滑动窗口吗！时间复杂度$O(n)$。写完后感觉那个while很刺眼，于是考虑能否把它去掉。

  • 想法3：可以记录每个对应的s[i]上次出现的位置的下一个位置，这样当更新到这个字符时直接“跳”到对应位置就可以了，时间复杂度也为$O(n)$，但是比较次数应该比上面的少。但是！提交后发现这样竟然比上面的做法慢！是因为数据的问题使每次更新最大值导致运算次数比上面的多了吗？

代码

  • 代码1：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0, tem = 0, now = 0, cnt[128];
        memset(cnt, 0, sizeof(cnt));
        for(int i = 0; i < s.length(); ++i)
        {
            if(cnt[s[i]])
            {
                res = max(res, tem);
                while(cnt[s[i]])
                {
                    --tem;
                    --cnt[s[now++]];
                }
            }
            ++tem;
            cnt[s[i]] = 1;
        }
        res = max(res, tem);
        return res;
    }
};
  • 代码2：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0, now = 0, idx[128];
        memset(idx, 0, sizeof(idx));
        for(int i = 0; i < s.length(); ++i)
        {
            now = max(idx[s[i]], now);
            res = max(res, i - now + 1);
            idx[s[i]] = i + 1;
        }
        return res;
    }
};

总结

太久没写，手生了啊。尽快捡起来吧。

Donate comment here
0%