天天演算法 | Medium | 7. 最長不重複子字元串：Longest Substring Without Repeating Characters

每天來一道，面試不卡殼，今天是天天演算法陪你成長的第7天

本題可在LeetCode上OJ，鏈接 Longest Substring Without Repeating Characters

今天的題目解題有Java 和 JavaScript 兩種語言版本，其中JS版本只有9行。

題目描述：

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

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", 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.

題目翻譯

給定一個字元串，找到不含重複字元的最長子串。

例子：

給定"abcabcbb"的答案是"abc"，長度是3。

給定"bbbbb"的答案是"b"，長度為1。

給定"pwwkew"的答案是"wke"，長度為3。請注意，答案必須是子字元串，"pwke"是子序列，而不是子字元串。

解題方案

標籤： String

思路：

• 遍歷字元串，使用 head 來標記當前子串的右側頭位置，tail 來標記當前子串的左側尾位置，sub[tail,head]表示當前子串
• 當sub[tail,head]中所有字元都不重複時，則head++
• 當sub[tail,head]中包含重複字元時，則tail++，直到所有字元都不重複為止
• 根據當前不重複子串，更新最大長度res

代碼：

class Solution { public int lengthOfLongestSubstring(String s) { HashSet<Character> hset = new HashSet(); int res = 0; int tail = 0; for(int head=0;head<s.length();head++){ while(tail<=head && hset.contains(s.charAt(head))){ hset.remove(s.charAt(tail)); tail++; } hset.add(s.charAt(head)); res = Math.max(res,head-tail+1); } return res;}

來放一個 LeetCode 上 9 行 JavaScript 版本的，用了JS的箭頭函數和函數式思想，很簡潔~

function lengthOfLongestSubstring(s) { const map = {}; var left = 0; return s.split("").reduce((max, v, i) => { left = map[v] >= left ? map[v] + 1 : left; map[v] = i; return Math.max(max, i - left + 1); }, 0);}

參考 9 line JavaScript solution

歡迎加入碼蜂社演算法交流群：天天一道演算法題

掃描下方二維碼或搜索「碼蜂社」公眾號，不怕錯過好文章：

最後求波點贊和關注~