网站制作过程内容网站建设 开票
LeetCode 3：寻找最长不含重复字符的子串长度
在字符串处理中，寻找最长不含重复字符的子串长度是一个经典问题。
问题描述
给定一个字符串 s ，我们需要找出其中不含有重复字符的最长子串的长度。
解决方案
我们可以使用滑动窗口的方法来解决这个问题。滑动窗口是一个区间，它可以通过两个指针来表示。在这个问题中，我们使用两个指针表示子串的左右边界。
我们使用一个哈希集合（unordered_set）来存储当前窗口中的字符，以便快速检查一个字符是否已经在当前窗口中。同时，我们使用两个指针 left 和 i 来表示当前窗口的左右边界，初始时都指向字符串的开头。
接下来，我们遍历字符串 s，对于每个字符，我们做如下操作：
- 如果当前字符已经在窗口中存在，我们需要将左指针
left移动到当前重复字符的下一个位置，以保证窗口中没有重复字符。 - 更新窗口中的字符集合，即将当前字符加入到集合中。
- 更新最长不含重复字符的子串的长度。
最终，我们返回最长子串的长度。
代码实现
class Solution {
public:int lengthOfLongestSubstring(string s) {if(s.size() == 0) return 0; // 如果字符串长度为0直接返回unordered_set<char> set;int maxStr = 0;int left = 0;for(int i = 0; i < s.length(); i++) {while(set.find(s[i]) != set.end()) {set.erase(s[left]);left++;}set.insert(s[i]);maxStr = max(maxStr, i - left + 1);}return maxStr;}
};
示例
让我们通过一个示例来说明上述算法的工作方式：
假设输入字符串为 "abcabcbb"，那么算法将按以下步骤执行：
- 遍历字符串，初始时
left = 0, maxStr = 0。 - 当
i = 0时，字符a不在集合中，加入集合，更新maxStr = max(maxStr, i - left + 1) = 1。 - 当
i = 1时，字符b不在集合中，加入集合，更新maxStr = max(maxStr, i - left + 1) = 2。 - 当
i = 2时，字符c不在集合中，加入集合，更新maxStr = max(maxStr, i - left + 1) = 3。 - 当
i = 3时，字符a在集合中，移动left指针到下一个位置，更新left = 1。 - 以此类推，直到遍历完整个字符串。
最终，返回 maxStr = 3，表示最长不含重复字符的子串长度为3。
对于给定字符串 s 的长度为 n，我们的算法使用了滑动窗口来寻找最长不含重复字符的子串长度。
复杂度分析
时间复杂度分析
- 遍历字符串： 算法需要遍历一次输入字符串
s，时间复杂度为 O(n)，其中 n 是字符串的长度。 - 滑动窗口操作： 在滑动窗口操作中，我们最多移动左指针
left和右指针i各一次。对于每个字符，我们在常数时间内检查是否在集合中，因此滑动窗口操作的时间复杂度为 O(1)。 - 因此，总体时间复杂度为 O(n)。
空间复杂度分析
- 哈希集合： 我们使用了一个哈希集合来存储当前窗口中的字符。在最坏情况下，集合中可能包含字符串中的所有字符，因此空间复杂度为 O(min(n, m))，其中 n 是字符串的长度，m 是字符集的大小（ASCII 字符集为 256）。
- 其他变量： 我们使用了常数个额外的变量，因此空间复杂度为 O(1)。
总结
通过滑动窗口的方法，我们可以在时间复杂度为 O(n) 的情况下解决这个问题。该方法利用了哈希集合的快速查找特性，使得算法具有高效性能和较好的扩展性，适用于处理大规模的字符串输入。