LeetCode算法解题集：Longest Substring

题目：
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.

思路：
使用map来保存每个字符出现的位置，key:字符，value:最后一次出现的位置，遍历一次后，保存该字符到map中，并同时保存一个max结果和当前计数的索引index，index取值是取最后一次重复任何一个字符出现的位置，max(取当前索引-最后一次出现位置)的最大值。算法复杂度：O(n)!!

代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s)
    {
        int max_result = 0;
        map<char, int> vaule_map;
        int index = -1;
        for (unsigned int i = 0; i < s.size(); i++)
        {
            map<char, int>::iterator iItr = vaule_map.find(s[i]);
            if (iItr != vaule_map.end())
            {
                index = iItr->second > index ? iItr->second : index;
            }
             
            max_result = (i - index) > max_result ? (i - index) : max_result;
             
            vaule_map[s[i]] = i;
        }
     
        return max_result;
    }
};

总结：
1、当你感觉一个算法很够复杂的时候，说明这个算法还不够顺通，真正优秀的算法是很简洁且高效的。
2、尽量减少中间变量，保证代码可读性。

本文摘录于海阔天空的博客，作者: zjg555543，发布时间: 2015-07-15