LeetCode题解(3)-- Longest Substring Without Repeating Characters

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.

就是找不含重复字符的最长子序列。

方法一，暴力搜索，超时:

先开始懒得动脑筋，就是想着循环string一遍，求出每个以s[i]为开头的不含重复子序列的最大长度，然后比较出最大的就是了。每次都是通过map查重。时间复杂度O（n^2），果然超时了。

 1 class Solution {
 2 public:
 3     int lengthOfLongestSubstring(string s) {
 4         map<char,bool> flag;
 5         int n=s.size(),count=0,tmp_count=0;
 6         for(int i=0;i<n;i++){
 7             tmp_count=0;
 8             flag.clear();
 9             for(int j=i;j<n;j++){
10                 if(flag.find(s[j])==flag.end()){
11                     tmp_count++;
12                     flag[s[j]]=true;
13                 }
14                 else{
15                     if(tmp_count>count)
16                         count=tmp_count;
17                     break;
18                 }
19             }
20         }
21         if(tmp_count>count)
22             count=tmp_count;
23         return count;
24     }
25 };

方法二：想了好久想到，直觉想法是map的val可以存东西，不要浪费掉，说白了就是空间换时间+剪枝。

降低时间复杂度的核心在于循环一遍string，依次找以i位置为结尾的不重最长子序列，利用性质，在位置i，只要看两个位置，一个是位置i-1为结尾的最长不重子序列的开头（存为begin），另一个是s[i]上次出现的位置（存在map里）。想了个大概就开始写写写，浪费了好久。

最后ac，发现代码真是简单，就是更新begin、map、count，所以梳理好算法再写很重要，包括条件判断和特殊情况！

 1 class Solution {
 2   public:
 3       int lengthOfLongestSubstring(string s) {
 4       map<char,int> pos;
 5        int begin=0,n=s.size(),count=0;
 6        for(int i=0;i<n;i++){
 7           if(pos.find(s[i])!=pos.end()){
 8                if(begin<=pos[s[i]])
 9                   begin=pos[s[i]]+1;　　//更新begin
10           }
11           if(i-begin+1>count)
12               count=i-begin+1;　　　　//更新count
13           pos[s[i]]=i;　　　　　　　　 //更新map
14      }
15      return count;
16      }
17  };