leetcode-Longest Substring Without Repeating Characters

题目链接：

https://leetcode.com/problems/longest-substring-without-repeating-characters/

开始思路是用一个hash记录字母以及相应的位置，用两指针的方法，一个指针指向头，一个指针往前走，当往前走的指针所指的字母在哈希表中出现过时，更新答案，同时更新指向头的指针；这里有一个trick，就是只有当原指向头指针的位置<重复字母所在的位置时，才更新该指针的位置，例如下面的case:

字符串为abba

头指针　　p1 = 0  hash[a] = 0

　　　　　p1 = 0  hash[b] = 1

　　　　   p1 = 2  hash[b] = 2

　　　　　p1 = 2  hash[a] = 3 (这里不能把p1更新成0，因为上一次头指针已经指向2了，说明前面出现的字符串是有重复的)

只有满足该指针的位置<hash[当前字符]时候，才能进行更新

AC代码如下：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = (int)s.size();
        int ans = 0;
        int idx = 0;
        unordered_map<char, int> maps;
        for(int i=0; i<n; ++i)
        {
            if(maps.find(s[i]) != maps.end())
            {
                if(idx  < maps[s[i]] + 1)
                {
                    idx = maps[s[i]] + 1;
                }
                
                if(i - idx + 1 > ans)
                {
                    ans = i - idx + 1;
                }
                maps[s[i]] = i;
            }
            else
            {
                if(i - idx + 1 > ans)
                {
                    ans = i - idx + 1;
                }
                maps.insert(make_pair(s[i], i));
            }
        }
        return ans;
    }
};

由于题目中的字母只有字符，因此hash也可以用一个char型的数组进行实现