leetcode——中级算法——数组和字符串——无重复字符的最长字串

给定一个字符串,找出不含有重复字符的最长子串的长度。
示例1

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

示例2

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

示例3

输入: "pwwkew"
输出: 3
解释: 无重复字符的最长子串是 "wke",其长度为 3。
     请注意,答案必须是一个子串,"pwke" 是一个子序列 而不是子串。

思路

设置保存当前不含重复元素的子串 sub=" ",设置字串的最大长度 maxLen = 0.
循环遍历每个字符c,若:

  1. 字串sub中不包含c,则将c加入sub,更新最大长度maxLen
  2. sub包含c,则需要删除sub中c及c之前的元素,然后将c加入sub。

最后返回maxLen即可。

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  let maxLen = 0;
  let sub = '';
  for (let c of s) {
    if (sub.includes(c)) {  // 子串中含有当前字符
      sub = sub.slice(sub.indexOf(c) + 1) + c;    // 将子串更新
    } else { // 不含
      sub += c;
      maxLen = Math.max(maxLen, sub.length);  // 更新最大长度
    }
  }
  return maxLen;
};
全部评论

相关推荐

11-28 17:58
门头沟学院 Java
美团 JAVA开发 n×15.5
牛客786276759号:百度现在晋升很难的 而且云这块的业务没美团好 你看百度股价都跌成啥样了
点赞 评论 收藏
分享
10-25 00:32
香梨想要offer:感觉考研以后好好学 后面能乱杀,目前这简历有点难
点赞 评论 收藏
分享
牛客868257804号:九个中铁八个中建
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务