记一次简单的算法题

题目：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
例子：输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

看到字符串取最长，我立马想到暴力循环法，理论上是每个位置的字符串都可以作为首位开始，所以只需要依次循环重复，直到出现重复子串。

/*
param: 用于判断的总字符串 
param: 循环开始位数
param: 初始字符串
*/
   let deff = function(s,c,str){
    for(let i =c;i<s.length;i++){
        if(str.indexOf(s[i]) ==-1){
            str+=s[i]
        }else{
            return [str.length, c+1]
        }
    }
    return [str.length, c+1]
}

对于传入的字符串，进行移位迭代

// 建立一个数组，依次存储从头开始的长度
let lengthOfLongestSubstring = function(s) { 
  let b = [];
  let initKey = 0;
  while(initKey<s.length){
      let temp = deff(s,initKey,str='');
      b.push(temp[0]);
      initKey = temp[1];
  }
  return b.sort((c,d)=>d-c).length ? b.sort((c,d)=>d-c)[0] : 0
};

暴力循环是解决了问题，但是是比较浅显的思想，有什么更好的呢？ 我们来再思索一下问题。
给定一个任意字符串，就以"abcabcbb"为例吧，我们看执行到"abc"的时候，暴力循环就记下这个长度3，然后从b开始继续循环，直到循环结束。但是我们会发现一点，第一次循环之后我们得到了“abc”,下一个是"a",我们完全可以排除首个a，以“bca”继续循环下去，没有必要在重新从无意义的循环开始，这个例子比较巧，刚好是首字母重叠，换个例子“abcb”,得到“ab”之后，完全没有必要再从“b”开始循环，因为得到的最大子串也不过是等于之前的子串长度。

let lengthOfLongestSubstring = function(s) { 
   let num = 0,res = 0;
   let m = '';
  for (n of s) {
    if (m.indexOf(n) == -1) {
      m += n;
      num++;
      res = res < num ? num: res;
    } else {
      m += n;
      m = m.slice(m.indexOf(n)+1);
      num = m.length;
    }
  }
  return res;
};

只需要对原字符串循环一次，就可以得到整个字符串中最大的子串长度。其实也比较好理解这个，想一想就能想到，只是我们一般不会考虑性能问题，是否存在浪费。我觉得这道题挺有意思，不难，但是提醒了我们编程人员，要深入去思考一个问题，不要只浮于表面。

对于字符串有很多有意思的题目，这其中有著名的“KMP”算法，还有比较小众的江湖戏称的“马拉车”Manacher算法，每一个算法都能水一章，蕴含的都是数学原理，只能说学无止境，大家苦海自渡，各凭本事。