[LeetCode]Longest Substring Without Repeating Characters

题意：给定一个字符串,查找最长的子串的长度（没有重复字符）。

原题来自：https://leetcode.com/problems/longest-substring-without-repeating-characters/

分析：

我自己的思路，和曾经做的求最长公共子串长度一样，不过那个是用二维数组，这个一维就ok了，其实就是一个hashtable。

 1 class Solution {
 2 public:
 3     int lengthOfLongestSubstring(string s) {
 4         int locs[256];//保存字符上一次出现的位置，由于有分字母，所以弄的这长度
 5         memset(locs, -1, sizeof(locs));
 6         //idx为当前子串的开始位置-1
 7         int idx = -1, max = 0;
 8         for (int i = 0; i < s.size(); i++)
 9         {
10             //如果当前字符出现过，那么当前子串的起始位置为这个字符上一次出现的位置+1
11             if (locs[s[i]] > idx)idx = locs[s[i]];
12             if (i - idx > max)max = i - idx;
13             locs[s[i]] = i;
14         }
15         return max;
16     }
17 };

作者：orange1438
出处：http://www.cnblogs.com/orange1438/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。