LeetCode刷题日记003——无重复最长子串

LeetCode3——无重复最长子串

完成时间：2022/09/15

题干

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
1
2
3
4
5

自己的思路

   由于题干要求无重复最长子串，因此很自然而然想到使用两个指针遍历字符串，那么无重复的关键词我们又自然而言想到数学中的集合。因此思路非常明确，只需要将我们遍历过的字符添加进集合，然后在查看下一个字符的时候看看集合中是否已经被包含进了集合中即可。如果被包含进了集合，那我们更新最大长度的记录变量maxLength，值为j-i，因为此时发生了重复，j的位置已经在重复字符串上，就恰好给我们补上了开头字符串的数目，因此实际上是j-i+1-1，就简化成了j-i。

   在测试的过程中遇到一种特殊情况，那就是例如"qwert0 *894/"这种从头到尾不重复的情况，由于不发生重复，因此也就不能根据是否包含进集合的条件来更新我们的maxLength，但我们考虑到这种情况下，一定是第二个指针已经指到字符串结尾了。所以我们可以最后加个判断，如果第二个指针到达了结尾，那我们就再更新一次maxLength，不过此时得是j-i+1，因为我们没有发生重复，且达到了字符串结尾，因此需要补上开头那个字符串。

   时间复杂度为O(n^2)。

#include 
#include 
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.length() <= 1) {
            return s.length();
        }

        set<char> charHash;
        int maxLength = 0;

        for (int i = 0; i < s.length()-1; i++) {
            charHash.insert(s[i]);
            for (int j = i + 1; j < s.length(); j++) {
                int exist = charHash.count(s[j]);
                charHash.insert(s[j]);
                if (exist) {
                    maxLength = maxLength > (j - i) ? maxLength : (j - i);  // 更新最大子串长度
                    break;
                }
                if (j == s.length() - 1) {
                    maxLength = maxLength > (j - i + 1) ? maxLength : (j - i + 1);  // 更新最大子串长度
                }
            }
            charHash.clear();
        }

        return maxLength;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

题解思路

   使用滑动窗，一个窗口左指针，一个窗口右指针，用一个集合保存窗口内的字符，如果发生重复则窗口左指针右移一位，并在集合中擦除被移调的字符。和自己的思路相似。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        set<char> charSet;
        int n = s.length();
        int rk = -1;    // 滑动窗的右指针
        int maxLength = 0;

        for (int i = 0; i < n; i++) {
            if (i != 0) {
                charSet.erase(s[i-1]);
            }

            while (rk < n-1 && !charSet.count(s[rk + 1])) {			// 右指针寻找有无重复字符
                charSet.insert(s[rk + 1]);
                rk++;
            }

            maxLength = max(maxLength, (rk - i + 1));
        }

        return maxLength;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

测试代码

#include "Solution.cpp"
#include 
using namespace std;

int main(void) {
	string s = "";
	Solution solution;

	int maxLength  = solution.lengthOfLongestSubstring(s);
	//cout << s.length();
	cout << maxLength;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14