时间轴

2025-11-11

init

题目：

P3 无重复字符的最长子串

https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-interview-150

滑动窗口，注意如果整个字符串没有重复字符这种情况

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
34
#include <string>
#include <unordered_set>
#include <algorithm>
using std::string;
using std::unordered_set;

// 给定一个字符串 s ，找出其中不含有重复字符的 最长 子串 的长度。
class Solution {
    public:
	int lengthOfLongestSubstring(string s)
	{
		int i = 0, j = 0;
		int n = s.size();
		unordered_set<char> uset;
		int len = 0;
		
		for (j = 0; j < n; j++) {
			if (uset.count(s[j])) {
				len = std::max(len, (int)uset.size());
				// 左边界收缩
				while (s[i] != s[j]) {
					uset.erase(s[i]);
					i++;
				}
				if (s[i] == s[j]) { //直到删除当前串
					uset.erase(s[i]);
					i++;
				}
			}
			uset.insert(s[j]);
		}
		return std::max(len, (int)uset.size());
	}
};

进入循环前先收缩左边界，直到满足是无重复字符的子串时才可以。

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
#include <string>
#include <unordered_set>

using std::string;
using std::unordered_set;

class Solution {
    public:
        int lengthOfLongestSubstring(string s)
        {
                int left = 0, right, n = s.size();
                int max_len = 0;
                unordered_set<char> uset;

                if (n == 0)
                        return 0;

                for (right = 0; right < n; right++) { // left index of window

                        // shrink window
                        while (uset.count(s[right])) {
                                uset.erase(s[left]);
                                left++;
                        }

                        uset.insert(s[right]);
                        
                        max_len = std::max(max_len, right - left + 1);
                }
                return max_len;
        }
};