LeetCode.3 无重复字符的最长子串(JS)

wthee 发布于2019-08-23 16:18 / 2257人阅读

摘要：先跳到第三题是因为第二题第一眼没读懂一题目无重复字符的最长子串给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例输入输出解释因为无重复字符的最长子串是，所以其长度为。以此来实现判断是否包含重复字符。

先跳到第三题是因为第二题第一眼没读懂

一、题目

无重复字符的最长子串：

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例1

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例2

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例3

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

二、我的答案

因为这道题之前在学校刷题的时候见过类似的，大概记得解法，就先放自己的思路

v1.0

/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
  let resultLength = 0
  function hasEchoChar(str){
    return new Set(str).size !== str.length ? true : false
  }
  let begin = 0, end = 1;
  while(end <= s.length) {
    if (!hasEchoChar(s.slice(begin, end))) {
      end - begin > resultLength ? resultLength = end - begin : null;
      end++
    } else {
      begin++ 
    }
  }
  return resultLength
};

讲解

两个指针用来遍历字符串，begin指向当前字符串的头，end指向当前字符串的下一位

let begin = 0, end = 1

如果当前字符串不包含重复字符串，则判断是否更新结果(resultLength)且end++，如果包含，begin++

if (!hasEchoChar(s.slice(begin, end ))) {
  end - begin > resultLength ? resultLength = end - begin : null;
  end++
} else {
  begin++ 
}

上文也说了之前碰到过类似的题，当时理解这部分用了好久，因为常写的循环都是只有一个指针变量的，像for(let i = 0; i < num; i++)，如果按照惯用思路肯定是循环套循环遍历所有子串，麻烦的丫批，上面这种写法妙就妙在一次循环中要么更新begin要么更新end，缩小了子串的筛选范围。

以示例3中的pwwkew为例，遍历的过程如下图

v2.0

写完v1.0代码，开心提交，通过是通过了，但是

我：？？？怎么肥四，一顿乱吹然后战胜8%，神仙打架？仔细分析了一下，发现是判断是否包含重复字符的函数hasEchoChar的问题，在v1.0代码中我把子串转化成set结构然后对比前后length是否相等，因为set自动去重的特性，如果相等则没有重复字符。以此来实现判断是否包含重复字符。(这么写的原因是上一题做完后去看了es6中Set和Map一章，上一题分析连接:我是链接)

function hasEchoChar(str){
    return new Set(str).size !== str.length ? true : false
}

估计耗时就是耗在了转化成set结构了，这样写本身并没错，但是他的作用是判断一个任意字符串是否含有重复字符，我们每次判断的是任意字符串吗？并不是，那就不应该继续采用这种方法。
聚光灯打到上文中展示遍历过程那张图，有重复字符的是pw->pww和wke->wkew，也就是说，只有每次end++时才有可能产生重复字符，也即是说我们只需要判断上次遍历的字符串是否包含这次新添加的字符即可，思路理清，代码如下

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  let resultLength = 0
  let begin = 0, end = 1
  while (end <= s.length) {
    let index = s.slice(begin, end - 1).indexOf(s[end - 1])
    if (index !== -1) {
      begin += (index + 1)
      end++
    } else {
      end - begin > resultLength ? resultLength = end - begin : null;
      end++
    }
  }
  return resultLength
};

同时做出优化的部分还有找到相同字串的情况

if (index !== -1) {
  begin += (index + 1)
  end++
}

在v1.0的代码中，每次找到相同字符就将begin指到下一个位置，如果还有呢，就再指向下一个位置，很明显begin可以一次指到位，即指到与当前子串末位相同字符位置的下一位，同时end++，开始下一轮的崭新循环。

       至此这道题我已经竭尽所能，执行用时从v1.0的956ms降低到v2.0的132ms，击败提交也从8.77%涨到71.88%。但是贪婪的我并不能满足于71.88%，于是去复制了一份耗时最低的答案自己提交，发现耗时140ms甚至比我的耗时还要多？去查了一下(查询结果)，可能原因为：1、服务器负载；2、测试用例增加。
       奥~~这样啊
       ~~那对不起，我的就是最佳答案~~

三、优秀答案

/**
 *. @param {string} s
 *. @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let substr = "", maxLength = 0;
    for (var i = 0; i < s.length; i++) {
        let findIndex = substr.indexOf(s[i]);
        if (~findIndex) {
            substr = substr.substring(findIndex + 1);
        }
        substr += s[i];
        if (substr.length > maxLength) {
            maxLength = substr.length;
        }
    }
    return maxLength;
};

按位取反~
之前从没见过~符号，搜了一下，是什么补码之类的，应该是大学计算机原理讲的东西(流下了悔恨的泪水)，感兴趣的小伙伴可以看一下这个js中怎么理解按位取反？

substring
功能和slice相同类似，同样，感兴趣的小伙伴可以看一下MDN中substring的定义

四、路漫漫其修远兮

云服务器 GPU云服务器最长公共子串 java最长相同子串字符串找子串算法字符串最大子串c语言

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/102881.html

【leetcode】3. 无重复字符的最长子串

摘要：示例输入输出解释因为无重复字符的最长子串是，所以其长度为。请注意，你的答案必须是子串的长度，是一个子序列，不是子串。完成循环后取队列中出现的最大长度即可。给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例 1：输入: abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是 abc，所以其长度为 3。示例 2：输入: bbbbb 输出: 1 解释:...

qc1iu 2019-08-23 18:32 评论0 收藏0
LeetCode 3——无重复字符的最长子串

摘要：题目解答方法一我们从前往后遍历字符串，代表最长子串的起始位置，一开始设置为零。如果没有遇到重复字符，则更新子串的长度，向后遍历。最长子串的起始位置重复的字符在子串中的位置初始化映射自动初始化为零获取更多精彩，请关注 1. 题目 showImg(https://segmentfault.com/img/remote/1460000016867082); 2. 解答 2.1. 方法一我们...

Rocture 2019-07-31 11:16 评论0 收藏0
力扣(LeetCode)3

摘要：示例输入输出解释因为无重复字符的最长子串是，所以其长度为。请注意，你的答案必须是子串的长度，是一个子序列，不是子串。若没有重复元素，则区间右边扩大，否则区间左边缩小。题目地址：https://leetcode-cn.com/probl...题目描述：给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例 1: 输入: abcabcbb输出: 3 解释: 因为无重复字符...

_DangJin 2019-08-16 15:43 评论0 收藏0
Leetcode 3 Longest Substring Without Repeat... 最长无

摘要：难度题意是求最长无重复子串给出一个字符串从所有子串中找出最长且没有重复字母的子串的长度我的解法是以为例使用一个记录当前子串遇到的所有字符用一个游标从头开始读取字符加入到中如果碰到了重复字符遇到了重复则从当前子串的头部的字符开始将该字符从中移 Longest Substring Without Repeating CharactersGiven a string, find the le...

RyanHoo 2019-08-14 17:01 评论0 收藏0
前端中等算法-无重复字符的最长子串

摘要：无重复字符的最长子串难度中等描述给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。输入输出解释因为无重复字符的最长子串是，所以其长度为。无重复字符的最长子串难度：中等描述：给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。样例：输入: abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是 abc，所以其长度为 3。输入: bbbbb ...

hyuan 2019-08-26 10:40 评论0 收藏0