面试经典150题 P3 无重复字符的最长子串

---

时间轴

时间轴

2025-11-11

init

滑动窗口

---

题目：

P3 无重复字符的最长子串

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

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

#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());
	}
};

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

#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;
        }
};

模板写法：

#include <string>
#include <unordered_map>
using std::string;
using std::unordered_map;

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

        // abcabcbb
        while (right < n) {
            umap[s[right]]++;
            right++;

            while (umap[s[right - 1]] > 1) {
                umap[s[left]]--;
                left++;
            }
            max_len = std::max(max_len, right - left);
        }

        return max_len;
    }
};