原题链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

一、题目描述

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

二、示例

示例 1

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

示例 2

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

示例 3

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

需要注意的是答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串

三、构造输入

根据题目的描述,javascript 可以构造一下几种输入情况:

  • const str = ' ';
  • const str = '';
  • const str = 'abcabcbb';
  • const str = 'au';
  • const str = 'pwwkew';

需要注意的是几个临界条件,因为会影响遍历,其中 ''' ''b' 都是临界条件之内

四、JavaScript 解题

以下并非最优解, 下面解法的时间复杂度是 O(n2)

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    const arr = Array.from(s); // 字符串构造数据
    const len = arr.length; // 长度
    if(len === 1) return 1; // 临界条件,如果长度是 1,不再需要计算
    let maxLen = 0; // 默认最大长度是 0 (这里是 0 的原因是下面便利的时候,是从 0 索引开始便利的)
    for (let index = 0; index < len - 1; index ++) { // 遍历 0 - len-1
        let str = `${arr[index]}`;  // 构造从 index 开始的字符串,每次都是从 index 开始
        for (let i = index + 1; i < len; i++) { // 遍历 index + 1 - len 
            if (str.indexOf(arr[i]) !== -1) { // 如果 str 已经包含了 index+n ,则当前 index 的遍历已经结束
                maxLen = str.length > maxLen ? str.length : maxLen; // 比较最大长度
                break;
            }
            str += arr[i]; // 如果当前并未包含 index+n 这个字符,需要拼接上去
            maxLen = str.length > maxLen ? str.length : maxLen; //  比较最大长度
        }
    }

    return maxLen;
};

我只做了一点小小优化就是第二次比较的时候,实际上比较的是 index + 1len ,因为前面已经不需要遍历了。

五、结果

1.jpg