原問題

Given a string, find the length of the?longest substring?without repeating characters.

Example 1: Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Example 2: Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. Example 3: Input: "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

我的沙雕解法

var lengthOfLongestSubstring = function(s) {let recordObj = {};let length = s.length;let max = 0;for(let i = 0; i < length; i++){let record = 0;for(let g = i; g < length; g++){if(recordObj[s[g]] === undefined){//無重復字母recordObj[s[g]] = true;record++;}else{//存在重復字母recordObj = {};break;}}max = record > max? record:max;if(max === length){break;}}return max; };

挨打：最暴力的無腦解法，耗時672ms。。。

貪心解法學習

參考了排名較前的答案，多數是貪心思想，以下摘抄一位的代碼并加上學習的注釋

/** * 通過i，j指針計算子序列長度 * j指針：表示當前循環的字母，i指針：表示起點 * map用于記錄出現過的字母的相鄰下標，給予i新的起點 * 重復字母出現時，比較當前起點與map的記錄位置，取較大值，保證連續子序列，同時體現貪心：求 * 當前可求得的最長子序列 **/ var lengthOfLongestSubstring = function(s) {var n = s.length, ans = 0;var map = new Map(); // 記錄出現過字母的相鄰下標// try to extend the range [i, j]for (var j = 0, i = 0; j < n; j++) {if (map.has(s.charAt(j))) { //若此字母在之前的循環中出現過i = Math.max(map.get(s.charAt(j)), i); //保證連續子序列，同時體現貪心}ans = Math.max(ans, j - i + 1); //比較map.set(s.charAt(j), j + 1); //記錄字母的相鄰位置}return ans; };

此算法耗時108ms
百度到一張圖片很有利于理解
舉例：qpxrjxkltzyx

圖片來源：https://www.cnblogs.com/wangk...

總結

以上是生活随笔為你收集整理的LeetCode——Longest Substring Without Repeating Characters的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。