leetcode3

 1 public class Solution
 2     {
 3         public int LengthOfLongestSubstring(string s)
 4         {
 5             var dic = new Dictionary<char, int>();
 6             var maxLength = 0;
 7             for (int i = 0; i < s.Length; i++)
 8             {
 9                 var c = s[i];
10                 if (!dic.ContainsKey(c))
11                 {
12                     dic.Add(c, i);
13                 }
14                 else
15                 {
16                     i = dic[c];
17                     var curLen = dic.Count;
18                     if (maxLength < curLen)
19                     {
20                         maxLength = curLen;
21                     }
22                     dic.Clear();
23                 }
24             }
25 
26             var lastLen = dic.Count;
27             if (maxLength < lastLen)
28             {
29                 maxLength = lastLen;
30             }
31             return maxLength;
32         }
33     }

这种解决方案思想是比较好的，但是实际的代码却引入了不必要的开销（如dic.Count的计算，dic.Clear()的处理等问题），因此执行效果不如普通的滑动窗口。

下面给出另一种执行效率更高的写法：

 1 public class Solution
 2     {
 3         public int LengthOfLongestSubstring(string s)
 4         {
 5             int n = s.Length, ans = 0;
 6             Dictionary<char, int> map = new Dictionary<char, int>();
 7             for (int j = 0, i = 0; j < n; j++)
 8             {
 9                 if (map.ContainsKey(s[j]))
10                 {
11                     //i记录没有出现重复字符的子串的起始索引
12                     i = Math.Max(map[s[j]], i);
13 
14                     //map记录每一个字符，当前循环为止的最大的索引+1,(+1是为方便计算)
15                     map[s[j]] = j + 1;
16                 }
17                 else
18                 {
19                     //新字符第一次出现，记录其索引+1,(+1是为方便计算)
20                     map.Add(s[j], j + 1);
21                 }
22                 ans = Math.Max(ans, j - i + 1);
23             }
24             return ans;
25         }
26     }

在补充一份python的实现：

 1 class Solution:
 2     def lengthOfLongestSubstring(self, s: str) -> int:
 3         n = len(s)
 4         if n == 0:
 5             return 0
 6         if n == 1:
 7             return 1
 8         dic = {}
 9         maxlength = 1
10         left = 0
11         right = 0
12         while left < n:
13             right = left
14             while right < n:
15                 if s[right] in dic and dic[s[right]] >= left:
16                     length = right - left
17                     maxlength = max(maxlength,length)
18                     left = dic[s[right]] + 1
19                     dic[s[right]] = right
20                     right += 1
21                 else:
22                     dic[s[right]] = right
23                     right += 1
24                     
25                 if right == n:
26                     length = right - left
27                     maxlength = max(maxlength,length)
28                     return maxlength
29         maxlength = max(maxlength,right-left)
30         return maxlength