免费做网站的网页,可以绑定域名的免费空间,如何别人看自己做的网站,鄱阳网站建设多少钱LeetCode 3#xff1a;寻找最长不含重复字符的子串长度
在字符串处理中#xff0c;寻找最长不含重复字符的子串长度是一个经典问题。
问题描述
给定一个字符串 s #xff0c;我们需要找出其中不含有重复字符的最长子串的长度。
解决方案
我们可以使用滑动窗口的方法来解…LeetCode 3寻找最长不含重复字符的子串长度
在字符串处理中寻找最长不含重复字符的子串长度是一个经典问题。
问题描述
给定一个字符串 s 我们需要找出其中不含有重复字符的最长子串的长度。
解决方案
我们可以使用滑动窗口的方法来解决这个问题。滑动窗口是一个区间它可以通过两个指针来表示。在这个问题中我们使用两个指针表示子串的左右边界。
我们使用一个哈希集合unordered_set来存储当前窗口中的字符以便快速检查一个字符是否已经在当前窗口中。同时我们使用两个指针 left 和 i 来表示当前窗口的左右边界初始时都指向字符串的开头。
接下来我们遍历字符串 s对于每个字符我们做如下操作
如果当前字符已经在窗口中存在我们需要将左指针 left 移动到当前重复字符的下一个位置以保证窗口中没有重复字符。更新窗口中的字符集合即将当前字符加入到集合中。更新最长不含重复字符的子串的长度。
最终我们返回最长子串的长度。
代码实现
class Solution {
public:int lengthOfLongestSubstring(string s) {if(s.size() 0) return 0; // 如果字符串长度为0直接返回unordered_setchar 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) 的情况下解决这个问题。该方法利用了哈希集合的快速查找特性使得算法具有高效性能和较好的扩展性适用于处理大规模的字符串输入。
