003. 無重複字符的最長子串 | Leetcode題解

2021-03-02 前端布道師
題目描述

給定一個字符串，請你找出其中不含有重複字符的 最長子串 的長度。

示例 1:

輸入: "abcabcbb"
輸出: 3
解釋: 因為無重複字符的最長子串是 "abc"，所以其長度為 3。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因為無重複字符的最長子串是 "b"，所以其長度為 1。
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因為無重複字符的最長子串是 "wke"，所以其長度為 3。
     請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。

難度：支持語言：JavaScript、Java、Python、C++相關標籤相關企業思路
題目要求連續， 我們考慮使用滑動窗口。而這道題就是窗口大小不固定的滑動窗口題目，然後讓我們求滿足條件的窗口大小的最大值，這是一種非常常見的滑動窗口題目。
算法：
用一個 hashmap 來建立字符和其出現位置之間的映射。同時維護一個滑動窗口，窗口內的都是沒有重複的字符，去儘可能的擴大窗口的大小，窗口不停的向右滑動。
如果當前遍歷到的字符從未出現過，那麼直接擴大右邊界；
如果當前遍歷到的字符出現過，則縮小窗口（左邊索引向右移動），然後繼續觀察當前遍歷到的字符；
維護一個全局最大窗口 res，每次用出現過的窗口大小來更新結果 res，最後返回 res 獲取結果;
(圖片來源：https://github.com/MisterBooo/LeetCodeAnimation)
維護數組：
使用一個數組來維護滑動窗口，遍歷字符串，判斷字符是否在滑動窗口數組裡
在則刪除滑動窗口數組裡相同字符及相同字符前的字符，然後將當前字符 push 進數組滑動窗口 暴力解法：暴力解法時間複雜度較高，會達到 O(n^2)O(n 2)，故而採取滑動窗口的方法降低時間複雜度定義一個 map 數據結構存儲 (k, v)，其中 key 值為字符，value 值為字符位置 +1，加 1 表示從字符位置後一個才開始不重複我們定義不重複子串的開始位置為 start，結束位置為 end隨著 end 不斷遍歷向後，會遇到與 [start, end] 區間內字符相同的情況，此時將字符作為 key 值，獲取其 value 值，並更新 start，此時 [start, end] 區間內不存在重複字符無論是否更新 start，都會更新其 map 數據結構和結果 ans。關鍵點滑動窗口記錄當前 index 開始的最大的不重複的字符序列複雜度分析代碼JavaScript 實現
/**
*  @作者：user7746o
*  @連結：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/zi-jie-leetcode3wu-zhong-fu-zi-fu-de-zui-chang-zi-/
*/
var lengthOfLongestSubstring = function(s) {
    let arr = [], max = 0
    for(let i = 0; i < s.length; i++) {
        let index = arr.indexOf(s[i])
        if(index !== -1) {
            arr.splice(0, index+1);
        }
        arr.push(s.charAt(i))
        max = Math.max(arr.length, max)
    }
    return max
};

/**
*  @作者：Heternally
*  @連結：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/javascriptjie-fa-chao-9998-by-heternally/
*/
var lengthOfLongestSubstring = function(s) {
  let num = 0,res = 0;
  let m = '';
  for (n of s) {
    if (m.indexOf(n) == -1) {
      m += n;
      num++;
      res = res < num ? num: res;
    } else {
      m += n;
      m = m.slice(m.indexOf(n)+1);
      num = m.length;
    }
  }
  return res;
};


C++ 實現
class Solution {
public:
    int lengthOfLongestSubstring(string s) {

        int ans = 0, start = 0;
        int n = s.length();
        //
        map<char, int> mp;

        for(int i=0;i<n;i++)
        {
            char alpha = s[i];
            if(mp.count(alpha))
            {
                start = max(start, mp[alpha]+1);
            }
            ans = max(ans, i-start+1);
            // 字符位置
            mp[alpha] = i;
        }

        return ans;
    }
};
/**
*  @作者：LeetCode-Solution
*  @連結：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/
*/
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 哈希集合，記錄每個字符是否出現過
        unordered_set<char> occ;
        int n = s.size();
        // 右指針，初始值為 -1，相當於我們在字符串的左邊界的左側，還沒有開始移動
        int rk = -1, ans = 0;
        // 枚舉左指針的位置，初始值隱性地表示為 -1
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指針向右移動一格，移除一個字符
                occ.erase(s[i - 1]);
            }
            while (rk + 1 < n && !occ.count(s[rk + 1])) {
                // 不斷地移動右指針
                occ.insert(s[rk + 1]);
                ++rk;
            }
            // 第 i 到 rk 個字符是一個極長的無重複字符子串
            ans = max(ans, rk - i + 1);
        }
        return ans;
    }
};

/**
*  @作者：pinku-2
*  @連結：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-cshi-xian-/
*/
class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        //s[start,end) 前面包含 後面不包含
        int start(0), end(0), length(0), result(0);
        int sSize = int(s.size());
        while (end < sSize)
        {
            char tmpChar = s[end];
            for (int index = start; index < end; index++)
            {
                if (tmpChar == s[index])
                {
                    start = index + 1;
                    length = end - start;
                    break;
                }
            }

            end++;
            length++;
            result = max(result, length);
        }
        return result;
    }
};

Java 實現暴力解法時間複雜度較高，會達到 O(n^2)O(n2 )，故而採取滑動窗口的方法降低時間複雜度定義一個 map 數據結構存儲 (k, v)，其中 key 值為字符，value 值為字符位置 +1，加 1 表示從字符位置後一個才開始不重複我們定義不重複子串的開始位置為 start，結束位置為 end隨著 end 不斷遍歷向後，會遇到與 [start, end] 區間內字符相同的情況，此時將字符作為 key 值，獲取其 value 值，並更新 start，此時 [start, end] 區間內不存在重複字符無論是否更新 start，都會更新其 map 數據結構和結果 ans。
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0, start = 0;
        int n = s.length();
        //
        Map<Character, Integer> map = new HashMap<>();

        for(int i=0;i<n;i++)
        {
            char alpha = s.charAt(i);
            if(map.containsKey(alpha))
            {
                start = Math.max(start, map.get(alpha)+1);
            }
            ans = Math.max(ans, i-start+1);
            // 字符位置
            map.put(alpha, i);
        }

        return ans;
    }
}
/**
*  @作者：guanpengchn
*  @連結：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/
*/
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int end = 0, start = 0; end < n; end++) {
            char alpha = s.charAt(end);
            if (map.containsKey(alpha)) {
                start = Math.max(map.get(alpha), start);
            }
            ans = Math.max(ans, end - start + 1);
            map.put(s.charAt(end), end + 1);
        }
        return ans;
    }
}


/**
*  @作者：VioletKiss
*  @連結：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/javati-jie-3wu-zhong-fu-zi-fu-de-zui-chang-zi-chua/
*/

class Solution {
 public int lengthOfLongestSubstring(String s) {
  int i = 0;
  int flag = 0;
  int length = 0;
  int result = 0;
  while (i < s.length()) {
   int pos = s.indexOf(s.charAt(i),flag);
   if (pos < i) {
    if (length > result) {
     result = length;
    }
    if (result >= s.length() - pos - 1) {
     return result;
    }
    length = i - pos - 1;
    flag = pos + 1;
   }
   length++;
   i++;
  }
  return length;
 }
}

Python3 實現
from collections import defaultdict


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        l = 0
        ans = 0
        counter = defaultdict(lambda: 0)

        for r in range(len(s)):
            while counter.get(s[r], 0) != 0:
                counter[s[l]] = counter.get(s[l], 0) - 1
                l += 1
            counter[s[r]] += 1
            ans = max(ans, r - l + 1)

        return ans

# @作者：powcai
# @連結：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-dong-chuang-kou-by-powcai/

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:return 0
        left = 0
        lookup = set()
        n = len(s)
        max_len = 0
        cur_len = 0
        for i in range(n):
            cur_len += 1
            while s[i] in lookup:
                lookup.remove(s[left])
                left += 1
                cur_len -= 1
            if cur_len > max_len:max_len = cur_len
            lookup.add(s[i])
        return max_len


# @作者：marcusxu
# @連結：連結：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/python3ti-jie-chao-jian-dan-de-dong-tai-gui-hua-ji/

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if s == '':
            return 0
        if len(s) == 1:
            return 1

        def find_left(s, i):
            tmp_str = s[i]
            j = i - 1
            while j >= 0 and s[j] not in tmp_str:
                tmp_str += s[j]
                j -= 1
            return len(tmp_str)
        length = 0
        for i in range(0, len(s)):
            length = max(length, find_left(s, i))
        return length

其他原題leetcode連結：3.longest-substring-without-repeating-characters合作方：JavaScript中文網 – 全球極客摯愛的技術成長平臺說明：leetcode 題解 | 每日一題🔥 所有題目並非全部為本人解答，部分為在複習學習中整理提取其他解題作者的優秀筆記，便於大家學習共同進步，如有侵權，請聯繫刪除。

相關焦點

  • LeetCode刷題筆記 - 3. 無重複字符的最長子串
    官方連結：https://leetcode-cn.com/problemset/all/一、題意難度：中等https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
  • 圖解LeetCode第 3 號問題:無重複字符的最長子串
    題目描述 給定一個字符串，找出不含有重複字符的最長子串的長度。示例 1:  輸入: "abcabcbb"   輸出: 3   解釋: 無重複字符的最長子串是 "abc"，其長度為 3。示例 2:  輸入: "bbbbb"  輸出: 1.     解釋: 無重複字符的最長子串是 "b"，其長度為 1。
  • LeetCode 熱題 HOT 100(02,無重複字符的最長子串)
    LeetCode 熱題 HOT 100（02，無重複字符的最長子串）不夠優秀，發量尚多，千錘百鍊，方可成佛。算法的重要性不言而喻，無論你是研究者，還是最近比較火熱的IT 打工人，都理應需要一定的算法能力，這也是面試的必備環節，算法功底的展示往往能讓面試官眼前一亮，這也是在大多數競爭者中脫穎而出的重要影響因素。
  • 整數反轉 | Leetcode題解
    難度：支持語言：JavaScript、Java、Python相關標籤相關企業思路 1:使用字符串在反轉並不是最好的選擇，因為還需要處理負號和0的情況，用數字運算方式反轉比較適合。解決溢出問題有兩個思路，第一個思路是通過字符串轉換加try catch的方式來解決，第二個思路就是通過數學計算來解決。由於字符串轉換的效率較低且使用較多庫函數，所以解題方案不考慮該方法，而是通過數學計算來解決。通過循環將數字x的每一位拆開，在計算新值時每一步都判斷是否溢出。
  • 算法連載之求解不含有重複字符的最長子串長度
    問題給定一個字符串，找出其中不含有重複字符的最長子串長度。示例 1:輸入:"abcabcbb"輸出:3解釋:因為無重複字符的最長子串是 "abc"，所以其長度為 3。示例 2:輸入:"bbbbb"輸出:1解釋:因為無重複字符的最長子串是 "b"，所以其長度為 1。
  • 每日一道算法題,讓你的頭腦更活躍(沒有重複字符的最長子串)
    沒有重複字符的最長子串給定一個字符串，查找不重複字符的最長子字符串的長度。解題思路看到題目，我們可以了解到，我們需要的是沒有重複字符的字符串，由此我想到了HashSet集合，我們可以利用它的特性來處理這道題目。
  • 經典leetcode算法題分享(字符串)
    我們可以先看看題解，看完思路再自己寫，千萬不要照抄，要自己想出來才能鍛鍊編程能力。所謂talking is cheap, show me code，那麼我們就從字符串開始吧！20.為什麼會這麼低的效率呢，其實想想就知道，我每次遍歷字符串就只刪一個有效的括號，如果出現類似這種"[[{}{}{}{}{}{}]]"，就會遍歷非常多次！所以不能這樣玩！怎麼刪效率比較高呢？最好是不要重複去遍歷，一次遍歷刪完效率是最高的。
  • 最長回文子串 | Leetcode題解
    題目描述給定一個字符串 s，找到 s 中最長的回文子串。你可以假設  s 的最大長度為 1000。5.longest-palindromic-substring解決這類問題的核心思想就是兩個字「延伸」，具體來說如果在一個不是回文字符串的字符串兩端添加任何字符，或者在回文串左右分別加不同的字符，得到的一定不是回文串
  • leetcode之字符串相加
    序本文主要記錄一下leetcode之字符串相加題目給定兩個字符串形式的非負整數 num1 和num2 ，計算它們的和。
  • [LeetCode] 943. Find the Shortest Superstring 找到最短的超級字符串
    A，讓我們找一個最短的字符串，使得所有A中的字符串是都該字符串的子串，並給了兩個例子。通過第一個例子可以發現，假如任意兩個字符串首尾沒有重複字母的話，其就是所有字符串直接連接起來即可。但是如果有重複字母的話，比如 abc 和 bca，二者連接起來就是 abca，而不是 abcbca 了，因為 bc 兩個字母是可以復用的，這是本題的難點。
  • LeetCode-87.擾亂字符串(Scramble String)
    擾亂字符串給定一個字符串 s1，我們可以把它遞歸地分割成兩個非空子字符串，從而將其表示為二叉樹。下圖是字符串 s1 = "great" 的一種可能的表示形式。例如，如果我們挑選非葉節點 "gr" ，交換它的兩個子節點，將會產生擾亂字符串 "rgeat" 。
  • LeetCode Weekly Contest 224 題解
    --InterviewProblem/blob/master/LeetCode/leetcode_number-of-rectangles-that-can-form-the-largest-square.cpp題解：模擬題。
  • 【記錄帖】(No.003)從零打卡刷Leetcode
    歡迎和小詹一起定期刷leetcode，每周一周五更新一題，每一題都吃透，歡迎一題多解，尋找最優解！題目大意：給出一個字符串，找到最長的沒有重複字符的子字符串，並返回該子字符串的長度。例如：Given "abcabcbb", the answer is "abc", which the length is 3.
  • 【每日leetcode】左旋轉字符串
    題目字符串的左旋轉操作是把字符串前面的若干個字符轉移到字符串的尾部。請定義一個函數實現字符串左旋轉操作的功能。比如，輸入字符串"abcdefg"和數字2，該函數將返回左旋轉兩位得到的結果"cdefgab"。
  • 另一道滑動窗口算法題【最長無重複子串】
    二 正文        題目：最長無重複子串Longest Substring Without Repeating Characters給定一個字符串，請找出其中無重複字符的最長子字符串。例如:"abcabcbb"，無重複字符的最長子字符串是"abc"，長度為3。
  • 最長公共前綴 | Leetcode題解
    題目描述:編寫一個函數來查找字符串數組中的最長公共前綴。如果不存在公共前綴，返回空字符串 "" 。難度：支持語言：JavaScript、Python、C++、Java相關標籤相關企業複雜度分析時間複雜度：O(mn)O(mn)，其中 mm 是字符串數組中的字符串的平均長度，nn 是字符串的數量。
  • 字節大佬Leetcode刷題筆記,看完吊打問你算法的面試官
    介紹leetcode 題解，記錄自己的 leetcode 解題之路。目前分為五個部分：第一個部分是 leetcode 經典題目的解析，包括思路，關鍵點和具體的代碼實現。而且 這些題目可以被記錄下來，日後會進行篩選添加到倉庫的題解模塊。第五部分是計劃， 這裡會記錄將來要加入到以上三個部分內容只有熟練掌握基礎的數據結構與算法，才能對複雜問題迎刃有餘。
  • 笨方法刷 leetcode(一)
    題目描述：實現一個算法，確定一個字符串 s 的所有字符是否全都不同示例 1：輸入: s = "leetcode"輸出: false>python中有一個內置函數set()，它的一個特性就是->可以利用已有列表、字符串、元組或字典的內容來創建集合，其中重複的值會被丟棄;所以就可以通過set()來得到一個剔除重複值後的集合，並且比較兩者的長度，如果長度相等，則證明字符唯一；如果長度不等，則字符不唯一代碼如下：class
  • LeetCode刷題實戰3:最長不重複子串
    https://leetcode.com/problems/longest-substring-without-repeating-characters/翻譯題目只有一句話：給定一個字符串，要求返回不包含重複字符的最長子串的長度。
  • LeetCode Weekly Contest 204 題解
    Detect Pattern of Length M Repeated K or More Times題目連結：https://leetcode.com/problems/detect-pattern-of-length-m-repeated-k-or-more-times/題解連結：https://github.com/yular/CC--InterviewProblem