首页 > 代码库 > LeetCode: Longest Substring Without Repeating Characters 题解

LeetCode: Longest Substring Without Repeating Characters 题解

2024-07-06 12:32:42   226人阅读

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.

题解：

使用贪心策略，Hash记录字符上一次出现的位置，并记录起点。

每次更新的时候，记得将start checkpoint 之间出现的字符location清空，以免重复。

 1 class Solution {
 2 public:
 3     int lengthOfLongestSubstring(string s) {
 4         int location[128],i,index,j;
 5         for(i=0;i<128;i++) location[i]=-1;
 6         int start=0,maxLength=0,templ=0;
 7         for(i=0;i<s.size();i++)
 8         {
 9              index = s[i];
10              if(location[index]== -1)
11                  templ++;
12              else
13              {
14                  if(templ>maxLength)
15                  {
16                       maxLength = templ;
17 //                      cout<<s.substr(start,templ)<<endl;
18                  }
19                  for(j=start;j<location[index];j++)
20                      location[s[j]]=-1;
21                  templ =templ - (location[index]-start);
22                  start = location[index]+1;
23              }
24              location[index]=i;
25         }
26         if(i==s.size() && templ>maxLength) maxLength=templ; 
27         return maxLength;         
28     }
29 };

转载请注明出处： http://www.cnblogs.com/double-win/


联系
我们