【滑动窗口+哈希表/数组记录】Leetcode 3. 无重复字符的最长子串

题目要求

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

子字符串是字符串中连续非空字符序列。

示例 1

输入：s = "abcabcbb"
输出：3
解释：无重复字符的最长子串是 "abc"，长度为 3。

示例 2

输入：s = "bbbbb"
输出：1
解释：无重复字符的最长子串是 "b"，长度为 1。

示例 3

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

提示

• 0 <= s.length <= 5 * 10^4
• s 由英文字母、数字、符号和空格组成

实际应用

文本编辑器中的应用

在文本编辑器中，用户输入文本时，编辑器需要实时检测是否有重复字符，以帮助用户避免输入错误。

数据流分析中的应用

在网络数据流分析中，需要实时检测数据流中的重复数据包，进行数据清洗和去重。

滑动窗口法

使用滑动窗口算法结合哈希表或数组来高效地记录和更新字符的位置，从而快速判断是否出现重复字符。

哈希表记录字符频率

#include <iostream>
#include <unordered_map>
#include <string>using namespace std;int lengthOfLongestSubstring(string s) {unordered_map<char, int> map;int left = 0, right = 0, res = 0;while (right < s.size()) {// 如果当前字符在map中存在，则更新left指针if (map.find(s[right]) != map.end()) {left = max(left, map[s[right]] + 1);}// 更新当前字符的索引map[s[right]] = right;right++;res = max(res, right - left);}return res;
}int main() {string s = "abcabcbb";cout << lengthOfLongestSubstring(s) << endl;return 0;
}

数组记录字符频率

#include <iostream>
#include <vector>
#include <string>using namespace std;int lengthOfLongestSubstring(string s) {vector<int> map(256, -1);int left = 0, right = 0, res = 0;while (right < s.size()) {// 如果字符重复，更新左边界if (map[s[right]] != -1) {left = max(left, map[s[right]] + 1);}// 更新字符的位置map[s[right]] = right;right++;res = max(res, right - left);    }return res;
}int main() {string s = "abcabcbb";cout << lengthOfLongestSubstring(s) << endl;return 0;
}

推荐一下

https://github.com/0voice