leetcode 3 题目解答 找出最长不包含重复字符的字符串的长度:给定一个字符串,找出其中最长不包含重复字符的字符串的长度。
分析
字符串问题一般的最优时间复杂度都是 O(n),即一次遍历字符串。考虑两个指针 i 和 j,i-j 维护一个不含重复字符的子字符串,maxLen 记录了当前符合条件的子字符串的最大长度。j 从字符串头部开始遍历字符串,并且判断当前字符是否已经出现过,据此更新 i 的位置以及 maxLen 的大小。
举个例子,"abcdbe",考虑一个时刻,i 指向'a',j 指向'b'。由于'b'已经出现过,i 需要从'a'一次遍历到'c',并且把沿途的字符全部置为未出现过;maxLen 初始的时候为 - 1,这时被更新为 max(-1, j - i) = 4。
代码
- class Solution {
- public: int lengthOfLongestSubstring(string s) {
- int i = 0,
- j = 0;
- int n = s.length();
- int maxLen = -1;
- bool exists[256] = {
- false
- };
- while (j < n) {
- if (exists[s[j]]) {
- maxLen = max(maxLen, j - i);
- while (s[i] != s[j]) {
- exists[s[i]] = false;
- i++;
- }
- i++;
- } else {
- exists[s[j]] = true;
- }
- j++;
- } // 考虑"abcd",j遍历完字符串之后,maxLen在while循环中并没有更新,需要在循环外更新一次 maxLen = max(maxLen, j - i); return maxLen; }};
总结
字符串的 O(n) 算法,一般来说是使用指针进行一次遍历。
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: