LeetCode-3.无重复的最长字串 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 时，若子串无重复，则更新最大长度。
代码实现

1. #include <unordered_set>
2. using namespace std;
4. class Solution {
5. public:
6.     int lengthOfLongestSubstring(string s) {
7.         int maxLen = 0;
8.         for (int i = 0; i < s.size(); ++i) {
9.             unordered_set<char> seen;
10.             for (int j = i; j < s.size(); ++j) {
11.                 if (seen.find(s[j]) != seen.end()) {
12.                     break;
13.                 }
14.                 seen.insert(s[j]);
15.                 maxLen = max(maxLen, j - i + 1);
16.             }
17.         }
18.         return maxLen;
19.     }
20. };

复制代码

复杂度分析

• 时间复杂度：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参加窗口→ 
  
• 输入 s = "pwwkew"：
  窗口会调整为 [p] → [pw] → 发现重复字符w，删除窗口起始位置到该重复字符之间的所有字符，将新w参加窗口→ [w]→[wk] → [wke] → 发现重复字符w，删除窗口起始位置到该重复字符之间的所有字符，将新w参加窗口 →[kew]
  
  1. class Solution {
  2. public:
  3.     int lengthOfLongestSubstring(string s) {
  4.         int Max_count = 0;
  5.       
  6.         vector<char >window;
  7.         vector<char>::iterator left = window.begin();
  8.         for (char c:s)  //在s中遍历每个字符
  9.         {
  10.             
  11.             vector<char>::iterator found = find(window.begin(), window.end(), c);
  12.             if (found!=window.end())
  13.             {
  14.                 window.erase(window.begin(), found + 1);
  15.             }
  16.             window.push_back(c);
  17.             Max_count = max(Max_count, (int)window.size());
  18.            
  19.         }
  20.         return Max_count;
  21.     }
  22. };

  复制代码
• 时间复杂度：O(n²)
  最坏情况下（如字符串无重复字符），每次插入新字符需遍历整个窗口。窗口长度最大为 n，总时间复杂度为 O(n²)。
  
• 空间复杂度：O(n)
  窗口 window 最多存储所有字符（当无重复时），空间复杂度为 O(n)。
  

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

为了高效判断字符是否重复，可以用一个哈希聚集或者哈希表来存储当前窗口中的字符及其位置。如果使用聚集的话，每次遇到重复字符时，必要不断移动左指针，并删除聚集中的字符，直到重复的那个字符被移出窗口。而如果使用哈希表记录字符的最新位置，大概可以更快调整左指针的位置。比如，可以用一个unordered_map<char, int>来生存每个字符最后出现的位置。当右指针j遍历到字符c时，如果c已经在map中，而且其位置大于即是当前左指针i的位置，那么就将i移动到该位置的下一个位置。然后更新map中c的位置为当前的j。同时，每次更新最大长度为j-i+1的最大值。
算法思绪：
因此，算法的步调可以总结为：
初始化i=0，max_len=0，创建一个unordered_map<char, int>来记录字符的位置。
遍历字符串中的每个字符，索引为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

1. #include <unordered_map>
2. #include <algorithm>
3. using namespace std;
5. class Solution {
6. public:
7.     int lengthOfLongestSubstring(string s) {
8.         unordered_map<char, int> charMap; // 存储字符及其最后出现的位置
9.         int maxLen = 0;
10.         int left = 0; // 滑动窗口的左边界
11.         
12.         for (int right = 0; right < s.size(); right++) {
13.             char currentChar = s[right];
14.             
15.             // 如果字符已存在且在窗口内，更新左边界
16.             if (charMap.find(currentChar) != charMap.end() && charMap[currentChar] >= left) {
17.                 left = charMap[currentChar] + 1;
18.             }
19.             
20.             charMap[currentChar] = right; // 更新字符位置
21.             maxLen = max(maxLen, right - left + 1); // 计算当前窗口长度并更新最大值
22.         }
23.         
24.         return maxLen;
25.     }
26. };

复制代码

复杂度分析

• 时间复杂度：O(n)，每个字符最多被访问两次（一次右指针，一次左指针）。
  
• 空间复杂度：O(min(m, n))，其中m为字符集巨细，最坏情况下必要存储所有不同字符的位置
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。