更新时间:2022-08-12 18:48:05
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without
repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
从左到右扫描,当遇到重复字母时,以上一个重复字母的index+1,作为新的搜索起始位置,直到最后一个字母。
/********************************* * 日期:2015-01-20 * 作者:SJF0115 * 题目: 3.Longest Substring Without Repeating Characters * 网址:https://oj.leetcode.com/problems/longest-substring-without-repeating-characters/ * 结果:AC * 来源:LeetCode * 时间复杂度:O(n) * 空间复杂度:O(1) * 博客: **********************************/ #include <iostream> #include <cstring> using namespace std; class Solution { public: int lengthOfLongestSubstring(string s) { int len = s.length(); if(len <= 1){ return len; }//if bool visited[256]; // 初始化 memset(visited,false,sizeof(visited)); // 计算 int max = 0,cur = 0,start = 0; for(int i = 0;i < len;){ // 没有元素和该元素重复 if(!visited[s[i]]){ visited[s[i]] = true; ++cur; ++i; }//if else{ // 更新最大长度 if(cur >= max){ max = cur; }//if cur = 0; memset(visited,false,sizeof(visited)); int index = 0; // 寻找之前重复元素的下一个元素的下标 for(int j = start;j < i;++j){ if(s[i] == s[j]){ index = j+1; break; }//if }//for start = index; i = index; } }//for if(cur > max){ max = cur; }//if return max; } }; int main(){ Solution solution; string str("abbacdafg"); int result = solution.lengthOfLongestSubstring(str); // 输出 cout<<result<<endl; return 0; }
class Solution { public: int lengthOfLongestSubstring(string s) { int len = s.length(); if(len <= 1){ return len; }//if // 记录上次出现的位置 int last[256]; // 初始化 memset(last,-1,sizeof(last)); // 计算 int max = 0,cur = 0,start = 0; for(int i = 0;i < len;++i){ // 有元素和该元素重复 if(last[s[i]] >= 0){ if(cur > max){ max =cur; }//if // 当遇到重复字母时,以上一个重复字母的index+1, // 作为新的搜索起始位置 i = last[s[i]] + 1; cur = 0; memset(last,-1,sizeof(last)); }//if ++cur; last[s[i]] = i; }//for if(cur > max){ max = cur; }//if return max; } };
对上一个思路继续进行优化。
在上一个思路中当遇到重复字母时,以上一个重复字母的index+1,作为新的搜索起始位置。上一个重复字母的下一个字母到当前字母可以不用重复遍历。
在本思路中搜索起点不是上一个重复字母的index+1而是当前字母。
通过记录上一个Lonest Substring Without Repeating Characters的起点,来计算出在当前字母时的长度。
class Solution { public: int lengthOfLongestSubstring(string s) { int len = s.length(); if(len <= 1){ return len; }//if // 记录上次出现的位置 int last[256]; // 初始化 memset(last,-1,sizeof(last)); // 计算 int max = 0,cur = 0,start = 0; for(int i = 0;i < len;++i){ int pos = (int)s[i]; // 有元素和该元素重复 if(last[pos] >= start){// not last[pos] >= 0 // 更新长度 cur = cur - (last[pos] - start); // 更新起点 start = last[pos] + 1; }//if else{ ++cur; } // 更新字符位置 last[pos] = i; if(cur > max){ max =cur; }//if }//for return max; } };
【LeetCode从零单排】No 3 Longest Substring Without Repeating Characters
[LeetCode] Longest Substring Without Repeating Characters 最长无重复子串
[LeetCode] Longest Substring with At Least K Repeating Characters 至少有K个重复字符的最长子字符串
[LeetCode] Longest Substring with At Most Two Distinct Characters 最多有两个不同字符的最长子串
[LeetCode] Longest Substring with At Most K Distinct Characters 最多有K个不同字符的最长子串
[LeetCode]--3. Longest Substring Without Repeating Characters
[LeetCode] Longest Substring with At Most Two Distinct Characters
LeetCode - 3. Longest Substring Without Repeating Characters