Loading... 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 <!--more--> ## 题目详解 ## ``` 示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 示例 2: 输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。 示例 3: 输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。 ``` ## 可行-穷举 ## 那么一开始肯定是最Lowwwwwww的了 ``` /** * @param {string} s * @return {number} */ var lengthOfLongestSubstring = function (s) { let result = [] let maxLength = 0 for (let i = 0; i < s.length; i++) { for (let j = i + 1; j <= s.length; j++) { result.push(s.slice(i, j)) } } result.forEach(array => { let temp for (let i = 0; i < array.length; i++) { temp = array.slice(0, i).concat(array.slice(i + 1)) if (temp.indexOf(array[i]) > -1) { return } } if (array.length > maxLength) { maxLength = array.length } }) return maxLength }; ``` ## 勉强能用-键值对 ## 1. 先外层遍历一次 2. 从外层遍历的起点开始往后新增字符,校验并记录满足条件的最大长度 ``` /** * @param {string} s * @return {number} */ var lengthOfLongestSubstring = function (s) { let map let maxLength = 0 for (let i = 0; i < s.length; i++) { map = Object.create(null) let length = 1 map[s[i]] = s[i] for (let j = i + 1; j < s.length; j++) { if (map[s[j]] !== undefined) { break } else { map[s[j]] = s[j] length++ } } if (length > maxLength) {maxLength = length} } return maxLength }; ``` ## 勉强能见人优化-滑块 ## 1. 从左至右滑动滑块,若新进字符(右)不重复,则不移除末尾字符(左) 2. 若新进字符与已存在字符重复,则移除左起点至被重复字符的字符字串, - 比如当前滑块为“abcde”,新进字符为c,则移除“abc” 3. 滑块右移,并比较当前长度与最大长度 ``` /** * @param {string} s * @return {number} */ var lengthOfLongestSubstring = function (s) { let _window = [] let maxLength = 0 let index = 0 let temp let tempIndex while (index < s.length) { temp = s[index] tempIndex = _window.indexOf(temp) if (tempIndex === -1) { _window.push(temp) if(_window.length > maxLength) { maxLength = _window.length} } else { _window.splice(0, tempIndex + 1) _window.push(temp) } index++ } return maxLength }; ``` ## 再优化 ## ``` /** * @param {string} s * @return {number} */ var lengthOfLongestSubstring = function (s) { if(!s) return 0; if(s.length == 1) return 1; let index, temp, len let arr = new Array(256) //在JavaScript中一个函数最多拥有255个参数 arr.fill(-1) let startIndex = 0 let maxLength = 0 for (let i = 0; i < s.length; i++) { temp = s[i].charCodeAt() index = arr[temp] if (index !== -1 && index >= startIndex) { len = i - startIndex if (len > maxLength) { maxLength = len } startIndex = index + 1 } arr[temp] = i } if (maxLength < (s.length - startIndex)) {maxLength = s.length - startIndex} return maxLength }; ``` [函数表达式][1] [1]: https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Operators/function Last modification:April 8, 2020 © Allow specification reprint Support Appreciate the author AliPayWeChat 赞 0 如果觉得文章对你有所收获,可以请笔者喝杯咖啡
2 comments
宝贝 你太强了
你在说什么骚话