LeetCode Go — 3. Самая длинная подстрока без повторяющихся символов

задняя часть алгоритм
LeetCode Go — 3. Самая длинная подстрока без повторяющихся символов

Это 18-й день моего участия в Gengwen Challenge.Подробности о мероприятии, пожалуйста, проверьте:Обновить вызов

Для лучшего будущего придерживайтесь чистки зубовLeetCode!

тема

Для заданной строки найдите длину самой длинной подстроки, не содержащей повторяющихся символов.

Пример 1:

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

Пример 2:

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

Пример 3:

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

Пример 4:

输入: s = ""
输出: 0

намекать:

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

Решение 1 — Скользящее окно

Идеи решения проблем

Сохраните каждый символ в хэш-таблице в каждом цикле, когда тот же символ будет найден в хэш-таблице, завершите цикл и сравните длину хэш-таблицы с длиной текущей самой длинной подстроки (начало с 0), возьмите больший, одновременно сбросить хеш-таблицу и перейти к следующему циклу.

Внешний цикл начинается с 0, а внутренний цикл начинается с индекса +1 внешнего цикла.

код

func lengthOfLongestSubstring(s string) int {
    m := make(map[byte]bool)
    l := 0
    for i, _ := range s {
        m[s[i]] = true
        for j := i+1; j < len(s); j++ {
            if _, found := m[s[j]]; found {
                if l < len(m) {
                    l = len(m)
                }
                m = make(map[byte]bool)
                break
            }
            m[s[j]] = true
        }
    }
    if l < len(m) {
        l = len(m)
    }
    return l
}

Результаты

执行用时：364 ms，在所有 Go 提交中击败了 5.03% 的用户
内存消耗：7 MB，在所有 Go 提交中击败了 5.29% 的用户

Анализ сложности

  • Временная сложность: O(N), гдеNэто длина строки. индексiиjКаждый будет проходить всю строку один раз.
  • Сложность пространства: O(∣Σ∣),вΣпредставляет набор символов (то есть символы, которые могут появляться в строке),∣Σ∣Указывает размер набора символов. Набор символов явно не указан в этом вопросе, поэтому по умолчанию он может использовать все символы, чьи коды ASCII находятся в [0, 128), т.е.∣Σ∣=128. Нам нужно использовать набор хэшей для хранения появившихся символов, а символы имеют не более∣Σ∣поэтому пространственная сложность равна O(∣Σ∣).

ссылка на тему

3. Самая длинная подстрока без повторяющихся символов

Категории