代码收藏家技术教程 2024-12-04

LeetCode题解：3.无重复字符的最长子串【Python 题解超详细，滑动窗口法、暴力解法】，知识拓展：哈希函数与哈希表

题目描述

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

代码

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """

        # 思路一：滑动窗口
        # 初始化最大长度记录
        max_length = 0
        # 初始化起始位置
        start_index = 0
        # 用于存储当前窗口内的字符
        char_set = set()

        # 遍历字符串，end_index作为窗口的右边界
        for end_index in range(len(s)):
            # 如果字符重复，缩小窗口的左边界，直到没有重复字符
            while s[end_index] in char_set:
                char_set.remove(s[start_index])  # 移除最左边的字符
                start_index += 1  # 移动左边界
            
            # 将当前字符加入集合
            char_set.add(s[end_index])
            # 更新最大长度
            max_length = max(max_length, len(char_set))

        return max_length

        # # 思路二：暴力解法
        # # 初始化最大长度记录
        # max_length = 0
        # # 遍历字符串的每一个起始位置，尝试从每个位置找到最长无重复子串
        # for start_index in range(len(s)):
        #     # 初始化当前子串，包含起始位置的字符
        #     sub_s = s[start_index]
        #     # 从 start_index 之后的字符开始，尝试构建无重复的子串
        #     for end_index in range(start_index + 1, len(s)):
        #         # 如果当前字符已在子串中，停止扩展子串
        #         if s[end_index] in sub_s:
        #             break
        #         else:
        #             # 如果没有重复字符，则将当前字符添加到子串中
        #             sub_s += s[end_index]

        #     # 更新最大长度，确保记录的是最长的无重复子串的长度
        #     max_length = max(max_length, len(sub_s))
        
        # return max_lengthh

思路一，暴力解法：其主要思路在于从左到右按顺序检查每个可能的子字符串。从字符串的每个位置开始，逐个扩展子串，检查是否包含重复字符。一旦遇到重复字符则停止扩展，记录当前无重复子串的长度，最终返回最长的长度。这种方法的时间复杂度较高，为 O( $n^2$ )，但易于理解其基本逻辑。

思路二，滑动窗口法：使用双指针和哈希集合形成滑动窗口，遇到重复字符时移动左指针缩小窗口，直至无重复，并不断向右拓展，更新最长无重复子串的长度。该方法时间复杂度为 O(n)，相比于前一种方法更高效。

知识拓展：哈希函数与哈希表

在前两篇文章中曾提到，python中的set与dict都是使用哈希表作为底层实现，今天我们就来简单讲一下什么是哈希函数，什么是哈希表。

哈希函数

哈希（Hash），又称散列，哈希函数又被称为散列函数。

定义

哈希函数是将任意长度的输入（或称消息）通过散列算法变换成固定长度的输出字符串的一种函数，这个输出字符串称为哈希值（Hash Value）或散列值。而究其本质而言，哈希函数实际上建立键（Key）与存储位置之间的映射关系。

特点

固定长度输出：无论输入数据的长度如何，哈希函数都会生成固定长度的输出值。
确定性：对于同一个输入，无论何时何地，使用相同的哈希函数总是得到相同的哈希值。
不可逆性：从哈希值很难反推出原始输入数据，这使得哈希函数在密码存储等领域具有广泛应用。

哈希函数在数据完整性验证、密码学、快速检索、数据同步等领域有广泛应用。

哈希表

定义

哈希表是一种通过哈希函数将键（Key）映射到表中一个位置以便快速访问记录的数据结构。它允许快速插入、删除和查找操作。

工作原理

键值映射：通过哈希函数将键映射到哈希表中的一个索引位置。
动态扩容：随着元素的增加，哈希表可能需要动态扩容以保持操作的效率

哈希函数建立了键（Key）与存储位置之间的映射关系，而哈希表则记录了这种关系。在哈希表中，哈希函数用于将键转换为哈希表中的一个索引，这个索引就是键对应的值的存储位置。

另外，关于哈希函数与哈希表还有一个非常重要的问题，哈希冲突，即不同的输入（键）经过哈希函数处理后得到了相同的输出（哈希值）。在哈希表中，这意味着两个或多个键将被映射到同一个存储位置，从而需要解决冲突以确保每个键都能正确地存储和检索。常用的冲突解决方法有链地址法（Chaining）、开放寻址法（Open Addressing）和线性探测（Linear Probing）等，感兴趣的同学可以深入了解下。

感谢你的阅读，希望对你有所帮助~

作者：爱编程的涵崽