LeetCode-3.无重复的最长字串 C++实现_leetcode 无重复字符的最长子串 c++

一.问题描述

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

示例 1:

输入: s = \"abcabcbb\"
输出: 3
解释: 因为无重复字符的最长子串是

\"abc\"，所以其长度为 3。

示例 2:

输入: s = \"bbbbb\"
输出: 1
解释: 因为无重复字符的最长子串是\"b\"，所以其长度为 1。

示例 3:

输入: s = \"pwwkew\"
输出: 3
解释: 因为无重复字符的最长子串是 \"wke\"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，\"pwke\" 是一个子序列，不是子串。

二.问题思路

 2.1暴力解法

检查所有可能的子串，然后判断每个子串是否有重复字符，记录下没有重复的最长子串的长度。这种方法的时间复杂度会比较高，因为要遍历所有子串，每个子串还要检查是否有重复。不过对于学习来说，暴力法有助于理解问题的基础解决方式。
实现过程：

1.外层循环确定子串的起始位置 i，内层循环确定子串的结束位置 j。

2.对于每个子串 s[i...j]，使用哈希集合记录已出现的字符。若 s[j] 已存在集合中，说明子串重复，终止当前内层循环；否则将 s[j] 加入集合。

3.每次扩展子串的右边界 j 时，若子串无重复，则更新最大长度。
代码实现

#include using namespace std;class Solution {public: int lengthOfLongestSubstring(string s) { int maxLen = 0; for (int i = 0; i < s.size(); ++i) { unordered_set seen; for (int j = i; j < s.size(); ++j) { if (seen.find(s[j]) != seen.end()) {  break; } seen.insert(s[j]); maxLen = max(maxLen, j - i + 1); } } return maxLen; }};

复杂度分析

• 时间复杂度：O(n²)，其中 n 为字符串长度。外层循环遍历 n 次，内层循环最多遍历 n 次，哈希集合的插入和查找操作均为 O(1)。

• 空间复杂度：O(min(n, m))，其中 m 为字符集大小（如 ASCII 字符集为 128）。哈希集合最多存储所有不同字符。

2.2 滑动窗口

维护一个动态窗口window，存储当前无重复字符的子串。

对于每个新字符c，检查是否在window中存在，存在则删除从窗口开始到该字符的所有元素（包括该字符），以消除重复。将c加入窗口,同时更新最大长度
示例：    

• 输入 s = \"abcabcbb\"：
  窗口依次为 [a] → [a,b] → [a,b,c] →发现重复字符a，删除窗口起始位置到该重复字符之间的所有字符,将新a加入窗口→ [b,c,a]  →发现重复字符b，删除窗口起始位置到该重复字符之间的所有字符,将新b加入窗口→ [c,a,b] → 发现重复字符c，删除窗口起始位置到该重复字符之间的所有字符,将新c加入窗口→ [abc]→ 发现重复字符b，删除窗口起始位置到该重复字符之间的所有字符,将新b加入窗口→ [cb]→ 发现重复字符b，删除窗口起始位置到该重复字符之间的所有字符,将新b加入窗口→ [b]

• 输入 s = \"pwwkew\"：
  窗口会调整为 [p] → [pw] → 发现重复字符w，删除窗口起始位置到该重复字符之间的所有字符，将新w加入窗口→ [w]→[wk] → [wke] → 发现重复字符w，删除窗口起始位置到该重复字符之间的所有字符，将新w加入窗口 →[kew]

  class Solution {public: int lengthOfLongestSubstring(string s) { int Max_count = 0;  vectorwindow; vector::iterator left = window.begin(); for (char c:s) //在s中遍历每个字符 { vector::iterator found = find(window.begin(), window.end(), c); if (found!=window.end()) { window.erase(window.begin(), found + 1); } window.push_back(c); Max_count = max(Max_count, (int)window.size());  } return Max_count; }};

• 时间复杂度：O(n²)
  最坏情况下（如字符串无重复字符），每次插入新字符需遍历整个窗口。窗口长度最大为 n，总时间复杂度为 O(n²)。

• 空间复杂度：O(n)
  窗口 window 最多存储所有字符（当无重复时），空间复杂度为 O(n)。

    2. 3 改良的滑动窗口（用哈希表实现） 

为了高效判断字符是否重复，可以用一个哈希集合或者哈希表来存储当前窗口中的字符及其位置。如果使用集合的话，每次遇到重复字符时，需要不断移动左指针，并删除集合中的字符，直到重复的那个字符被移出窗口。而如果使用哈希表记录字符的最新位置，可能可以更快调整左指针的位置。比如，可以用一个unordered_map来保存每个字符最后出现的位置。当右指针j遍历到字符c时，如果c已经在map中，并且其位置大于等于当前左指针i的位置，那么就将i移动到该位置的下一个位置。然后更新map中c的位置为当前的j。同时，每次更新最大长度为j-i+1的最大值。

算法思路：

因此，算法的步骤可以总结为：

初始化i=0，max_len=0，创建一个unordered_map来记录字符的位置。

遍历字符串中的每个字符，索引为j：

- 如果s[j]已经在map中，并且map[s[j]] >= i，那么将i设置为map[s[j]] + 1。

- 更新map[s[j]]为j。

- 计算当前窗口的长度j - i +1，如果大于max_len，则更新max_len。

这样，最终返回max_len。

示例3中的s=\"pwwkew\"。初始化i=0，max=0。map为空。

j=0，字符p，不在map中。map[p]=0。max=1.

j=1，字符w，不在map中。map[w]=1. max=2.

j=2，字符w。此时，map中存在w，位置1 >=i=0。所以i=1+1=2。更新map[w]=2。窗口长度是2-2+1=1。max还是2.

j=3，字符k。不在map中。map[k]=3。窗口长度3-2+1=2。max还是2.

j=4，字符e。不在map中。map[e]=4。窗口长度4-2+1=3。max更新为3.

j=5，字符w。此时，map中w的值是2。i当前是2。map[w] >=i吗？是的。所以i=2+1=3。更新map[w]=5。窗口长度5-3+1=3。max保持3

#include #include using namespace std;class Solution {public: int lengthOfLongestSubstring(string s) { unordered_map charMap; // 存储字符及其最后出现的位置 int maxLen = 0; int left = 0; // 滑动窗口的左边界 for (int right = 0; right = left) { left = charMap[currentChar] + 1; } charMap[currentChar] = right; // 更新字符位置 maxLen = max(maxLen, right - left + 1); // 计算当前窗口长度并更新最大值 } return maxLen; }};