Sunday, January 18, 2015

[LeetCode]Longest Substring Without Repeating Characters


仍然是双指针是的方法,这里我们只需要维护一个set来判断有没有重复的character就可以,左指针的移动策略如下:
  • 如果right指向的字符不在set里,更新set,看当前substring是不是更长,更长就把结果设为当前substring
  • 如果right指向的字符在set里,左移left直到移除和当前right指向的那个字符一样的字符为止,更新set,看当前substring是不是更长,更长就把结果设为当前substring
时间复杂度是O(n),代码如下:

No comments:

Post a Comment