Longest Substring Without Repeating Characters

---

Given a string, find the length of the longest substring without repeating characters.

Example:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

---

题目大意

这题求一个字符串里面没有重复字母的最长子串

Solution1： 双重循环

var lengthOfLongestSubstring = function (s) {
    var max = 0;

    for (var i = 0; i < s.length; i++) {
        var mSet = new Set();
        if (max > s.length - i) {
            break;
        }
        for (var j = i; j < s.length; j++) {
            if (!mSet.has(s[j])) { //找不到重复元素的时候，记录元素和元素个数
                mSet.add(s[j]);
                max = Math.max(max, mSet.size);
            } else { //找到重复元素时，清空记录元素（注意要留下当前元素）
                mSet.clear();
                mSet.add(s[j]);
            }
        }
    }
    console.log(max);
    return max;  
};

先把字符串变成数组，然后从第一个元素开始，定义一个指针j，j依次向后搜索，找不到重复元素的时候，记录元素和元素个数，当找到重复元素时，清空记录元素（注意要留下当前元素）。
遍历数组完成后，再从第二个元素开始遍历。注意如果已经得到的最长子串大于剩余元素个数的时候，就跳出循环。
复杂度是 O(n^2) 可能会超时，所以强烈不推荐。

Solution2 超强大神版

'use strict';
var lengthOfLongestSubstring = function (s) {
    let dict = {}; // 字典里面存放每个元素以及元素所在的位置
    let maxLen = 0, start = -1;
    for (let i = 0; i < s.length; i++) {
        if (dict[s[i]] > start)
            start = dict[s[i]];
        dict[s[i]] = i;
        maxLen = Math.max(maxLen, i - start);
    }
    return maxLen;
}

在leetcode的答案中找到了一个大神写的c++算法，简直不能再D，因此改成JavaScript版。

解析：首先定义一个字典存放每个元素以及元素的位置，当有重复的元素出现时，更改元素位置，并且比较当前元素位置与上次出现位置的距离。

---

刚刚入门算法，大神莫喷，欢迎指正。