力扣00003.无重复字符的最长子串

发表于 分类于 阅读次数： 本文字数： 1.8k 阅读时长 ≈ 7 分钟
无重复字符的最长子串、哈希表、字符串、滑动窗口、中等

题目描述

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

示例 1：

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2：

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3：

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

提示：

  • $0 <= s.length <= 5 * 10^4$
  • s 由英文字母、数字、符号和空格组成

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> charIndex;
        int maxLength = 0, start = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (charIndex.find(s[i]) != charIndex.end() && charIndex[s[i]] >= start) {
                start = charIndex[s[i]] + 1;
            } else {
                maxLength = max(maxLength, i - start + 1);
            }
            charIndex[s[i]] = i;
        }
        return maxLength;
    }
};

结果

执行用时 : 12 ms, 击败 81.24% 使用 C++ 的用户

内存消耗 : 8.53 MB, 击败 67.64% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> charIndex = new HashMap<>();
        int maxLength = 0, start = 0;
        for (int i = 0; i < s.length(); i++) {
            char currentChar = s.charAt(i);
            if (charIndex.containsKey(currentChar) && charIndex.get(currentChar) >= start) {
                start = charIndex.get(currentChar) + 1;
            } else {
                maxLength = Math.max(maxLength, i - start + 1);
            }
            charIndex.put(currentChar, i);
        }
        return maxLength;
    }
}

结果

执行用时 : 5 ms, 击败 63.77% 使用 Java 的用户

内存消耗 : 43.25 MB, 击败 7.96% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        char_index = {}
        max_length = start = 0
        for i, char in enumerate(s):
            if char in char_index and char_index[char] >= start:
                start = char_index[char] + 1
            else:
                max_length = max(max_length, i - start + 1)
            char_index[char] = i
        return max_length

结果

执行用时 : 36 ms, 击败 94.92% 使用 Python 的用户

内存消耗 : 13.45 MB, 击败 66.22% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_index = {}
        max_length = start = 0
        for i, char in enumerate(s):
            if char in char_index and char_index[char] >= start:
                start = char_index[char] + 1
            else:
                max_length = max(max_length, i - start + 1)
            char_index[char] = i
        return max_length

结果

执行用时 : 48 ms, 击败 99.64% 使用 Python3 的用户

内存消耗 : 18.11 MB, 击败 5.01% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int lengthOfLongestSubstring(char* s) {
    int charIndex[128];
    int maxLength = 0, start = 0;
    for (int i = 0; i < 128; i++) {
        charIndex[i] = -1;
    }
    for (int i = 0; s[i] != '\0'; i++) {
        char currentChar = s[i];
        if (charIndex[currentChar] >= start) {
            start = charIndex[currentChar] + 1;
        } else {
            maxLength = (i - start + 1) > maxLength ? (i - start + 1) : maxLength;
        }
        charIndex[currentChar] = i;
    }
    return maxLength;
}

结果

执行用时 : 4 ms, 击败 83.04% 使用 C 的用户

内存消耗 : 6.39 MB, 击败 81.61% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int LengthOfLongestSubstring(string s) {
        int[] charIndex = new int[128];
        int maxLength = 0, start = 0;
        for (int i = 0; i < 128; i++) {
            charIndex[i] = -1;
        }
        for (int i = 0; i < s.Length; i++) {
            char currentChar = s[i];
            if (charIndex[currentChar] >= start) {
                start = charIndex[currentChar] + 1;
            } else {
                maxLength = Math.Max(maxLength, i - start + 1);
            }
            charIndex[currentChar] = i;
        }
        return maxLength;
    }
}

结果

执行用时 : 44 ms, 击败 99.93% 使用 C# 的用户

内存消耗 : 40.70 MB, 击败 27.18% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let charIndex = {};
    let maxLength = 0;
    let start = 0;
    for (let i = 0; i < s.length; i++) {
        let char = s[i];
        if (charIndex[char] !== undefined && charIndex[char] >= start) {
            start = charIndex[char] + 1;
        } else {
            maxLength = Math.max(maxLength, i - start + 1);
        }
        charIndex[char] = i;
    }
    return maxLength;
};

结果

执行用时 : 84 ms, 击败 59.77% 使用 JavaScript 的用户

内存消耗 : 46.90 MB, 击败 30.01% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function lengthOfLongestSubstring(s: string): number {
    let charIndex: { [key: string]: number } = {};
    let maxLength = 0;
    let start = 0;
    for (let i = 0; i < s.length; i++) {
        let char = s[i];
        if (charIndex[char] !== undefined && charIndex[char] >= start) {
            start = charIndex[char] + 1;
        } else {
            maxLength = Math.max(maxLength, i - start + 1);
        }
        charIndex[char] = i;
    }
    return maxLength;
}

结果

执行用时 : 88 ms, 击败 58.76% 使用 TypeScript 的用户

内存消耗 : 47.76 MB, 击败 38.63% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s) {
        $charIndex = [];
        $maxLength = 0;
        $start = 0;
        for ($i = 0; $i < strlen($s); $i++) {
            $char = $s[$i];
            if (array_key_exists($char, $charIndex) && $charIndex[$char] >= $start) {
                $start = $charIndex[$char] + 1;
            } else {
                $maxLength = max($maxLength, $i - $start + 1);
            }
            $charIndex[$char] = $i;
        }
        return $maxLength;
    }
}

结果

执行用时 : 20 ms, 击败 49.42% 使用 PHP 的用户

内存消耗 : 19.57 MB, 击败 10.46% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var charIndex = [Character: Int]()
        var maxLength = 0
        var start = 0
        for (i, char) in s.enumerated() {
            if let index = charIndex[char], index >= start {
                start = index + 1
            } else {
                maxLength = max(maxLength, i - start + 1)
            }
            charIndex[char] = i
        }
        return maxLength
    }
}

结果

执行用时 : 16 ms, 击败 62.76% 使用 Swift 的用户

内存消耗 : 15.63 MB, 击败 5.14% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    fun lengthOfLongestSubstring(s: String): Int {
        val charIndex = mutableMapOf<Char, Int>()
        var maxLength = 0
        var start = 0
        for (i in s.indices) {
            val char = s[i]
            if (charIndex.containsKey(char) && charIndex[char]!! >= start) {
                start = charIndex[char]!! + 1
            } else {
                maxLength = maxLength.coerceAtLeast(i - start + 1)
            }
            charIndex[char] = i
        }
        return maxLength
    }
}

结果

执行用时 : 208 ms, 击败 60.94% 使用 Kotlin 的用户

内存消耗 : 36.87 MB, 击败 39.48% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    int lengthOfLongestSubstring(String s) {
    Map<String, int> charIndex = {};
    int maxLength = 0, start = 0;
    for (int i = 0; i < s.length; i++) {
        String char = s[i];
        if (charIndex.containsKey(char) && charIndex[char]! >= start) {
        start = charIndex[char]! + 1;
        } else {
        maxLength = maxLength > i - start + 1 ? maxLength : i - start + 1;
        }
        charIndex[char] = i;
    }
    return maxLength;
    }
}

结果

执行用时 : 352 ms, 击败 41.18% 使用 Dart 的用户

内存消耗 : 147.63 MB, 击败 97.06% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
func lengthOfLongestSubstring(s string) int {
    charIndex := make(map[byte]int)
    maxLength, start := 0, 0
    for i := 0; i < len(s); i++ {
        if index, exists := charIndex[s[i]]; exists && index >= start {
            start = index + 1
        } else {
            maxLength = max(maxLength, i-start+1)
        }
        charIndex[s[i]] = i
    }
    return maxLength
}

结果

执行用时 : 4 ms, 击败 88.47% 使用 Go 的用户

内存消耗 : 3.07 MB, 击败 23.56% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# @param {String} s
# @return {Integer}
def length_of_longest_substring(s)
    char_index = {}
    max_length = start = 0
    s.each_char.with_index do |char, i|
        if char_index.key?(char) && char_index[char] >= start
            start = char_index[char] + 1
        else
            max_length = [max_length, i - start + 1].max
        end
        char_index[char] = i
    end
    max_length
end

结果

执行用时 : 80 ms, 击败 100.00% 使用 Ruby 的用户

内存消耗 : 206.75 MB, 击败 15.79% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
object Solution {
  def lengthOfLongestSubstring(s: String): Int = {
    var charIndex = Map[Char, Int]()
    var maxLength = 0
    var start = 0
    for (i <- s.indices) {
      val char = s(i)
      if (charIndex.contains(char) && charIndex(char) >= start) {
        start = charIndex(char) + 1
      } else {
        maxLength = maxLength.max(i - start + 1)
      }
      charIndex += (char -> i)
    }
    maxLength
  }
}

结果

执行用时 : 596 ms, 击败 38.89% 使用 Scala 的用户

内存消耗 : 58.82 MB, 击败 5.55% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
use std::collections::HashMap;

impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        let mut char_index = HashMap::new(); // 用于存储字符的索引
        let mut max_length = 0;
        let mut start = 0;
        for (i, c) in s.chars().enumerate() {
            if let Some(&index) = char_index.get(&c) {
                if index >= start {
                    start = index + 1;
                }
            }
            max_length = max_length.max(i - start + 1);
            char_index.insert(c, i);
        }
        max_length as i32
    }
}

结果

执行用时 : 4 ms, 击败 69.79% 使用 Rust 的用户

内存消耗 : 2.14 MB, 击败 61.59% 使用 Rust 的用户

Racket

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(define (length-of-longest-substring s)
  (define left 0)
  (define cur-len 0)
  (define max-len 0)
  (define lookup (mutable-set))

  (define (update-lengths! c)
    (let loop ()
      (when (set-member? lookup c)
        (set-remove! lookup (string-ref s left))
        (set! left (+ left 1))
        (set! cur-len (- cur-len 1))
        (loop))))
  
  (for ([c s])
    (update-lengths! c)
    (set-add! lookup c)
    (set! cur-len (+ cur-len 1))
    (set! max-len (max cur-len max-len)))
  
  max-len)

结果

执行用时 : 224 ms, 击败 66.67% 使用 Racket 的用户

内存消耗 : 99.09 MB, 击败 66.67% 使用 Racket 的用户

Erlang

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
-spec length_of_longest_substring(S :: unicode:unicode_binary()) -> integer().
length_of_longest_substring(S) ->
    StrList = unicode:characters_to_list(S),
    the_max_length(StrList, 0, queue:new(), sets:new([{version, 2}]), 0).
the_max_length([Char | RestChars], Length, Window, CharSet, MaxLength) ->
    case sets:is_element(Char, CharSet) of
        false ->  
            the_max_length(RestChars, Length + 1, queue:in(Char, Window), sets:add_element(Char, CharSet), MaxLength);
        true -> 
            {CharSet1, Win1} = remove_from_window(CharSet, Window, Char),
            the_max_length(RestChars, queue:len(Win1) + 1, queue:in(Char, Win1), sets:add_element(Char, CharSet1), max(MaxLength, Length))
    end;
the_max_length([], Length, _, _, MaxLength) -> max(MaxLength, Length).
remove_from_window(CharSet, Window, Char) ->
    case queue:is_empty(Window) of
        true -> {CharSet, Window};
        false ->
            {{value, W}, Win1} = queue:out(Window),
            CharSet1 = sets:del_element(W, CharSet),
            case sets:is_element(Char, CharSet1) of
                true -> 
                    remove_from_window(CharSet1, Win1, Char);
                false -> {CharSet1, Win1}
            end
    end.

结果

执行用时 : 300 ms, 击败 100.00% 使用 Erlang 的用户

内存消耗 : 58.43 MB, 击败 100.00% 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户