1.两数之和

答案

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        num_dict = {}
        for i, num in enumerate(nums):
            need = target - num

            if need in num_dict:
                return [num_dict[need], i]

            num_dict[num] = i

注意

要求返回两个数的数组下标

解法：哈希表 / 字典

字典和哈希表的关系

哈希表是底层的“数据结构”，而字典是 Python 语言中基于哈希表实现的一种“高级抽象”。

字典

一种无序（注：Python 3.7+ 已保证插入顺序）、可变的数据结构，专门用于存储键值对（Key-Value Pairs）。

1. 字典的核心特性

• 键（Key）必须唯一且不可变：键可以是字符串、数字或元组，但绝对不能是列表或字典。
• 值（Value）可以是任意类型：数字、字符串、列表、甚至另一个字典（嵌套字典）都可以。
• 极高的查询效率：正如我们之前聊到的，字典底层基于哈希表，无论数据量多大，查找、添加、删除的时间复杂度几乎都接近 O(1)。
• 有序性（Python 3.7+）：在 Python 3.7 及以后的版本中，字典会严格记住并保留你添加键值对的先后顺序。

2.字典的基本操作

##########################创建字典##########################
# 使用花括号
user = {"name": "Alice", "age": 25}

# 使用 dict() 构造函数
user2 = dict(name="Bob", age=30)
##########################增删查改##########################
# 查：推荐使用 get()，键不存在时返回 None 或默认值，不会报错
print(user.get("name"))        # 输出: Alice
print(user.get("gender", "未知")) # 输出: 未知

# 增 / 改：键不存在则新增，存在则修改
user["email"] = "alice@test.com"  
user["age"] = 26                

# 删：删除指定键，或清空整个字典
del user["email"]
user.pop("age")               # 删除并返回被删除的值
user.clear()                  # 清空字典
##########################遍历字典的三种方式##########################
my_dict = {"a": 1, "b": 2, "c": 3}

# 1. 遍历键（默认行为）
for key in my_dict:
    print(key)

# 2. 遍历键和值（最常用，使用 items()）
for key, value in my_dict.items():
    print(f"{key}: {value}")

# 3. 只遍历值
for value in my_dict.values():
    print(value)
##########################字典推导式##########################
# 快速生成 {1: 1, 2: 4, 3: 9}
squares = {x: x**2 for x in range(1, 4)}
##########################什么时候该用字典？##########################
# 当你需要频繁查找数据时（替代在列表里进行低效的 for 循环遍历）。
# 当你需要统计频次时（例如：统计一篇文章中每个单词出现的次数）。
# 当你需要表达映射关系或记录对象状态时（例如：学号对应姓名，IP地址对应主机名）。

enumerate函数

核心作用是：在遍历一个可迭代对象（如列表、元组、字符串等）时，同时获取元素的“索引（下标）”和“元素值”。

# 基本语法
enumerate(iterable, start=0)
# iterable：要遍历的对象（列表、字符串、字典的键等）。
# start：索引的起始值，默认为 0。你可以设置为 1 或其他数字。

2.两数之和

答案

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        # 构造哑巴节点 dummy，最后返回 dummy.next, 以方便处理新链表的头节点。
        dummy = ListNode(0) # 链表节点
        node = dummy  # node 一直会变化（前进）
        carrier = 0  # 进位

        # 只要有没走到头的链表或者进位不为 0 就一直前进。
        while l1 or l2 or carrier:
            # 求和，考虑可能有链表走到头
            sum = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carrier

            # 在尾部添加节点
            node.next = ListNode(sum % 10)
            node = node.next
            
            # 更新进位，并向两个链表尾部前进
            carrier = sum // 10
            if l1: l1 = l1.next
            if l2: l2 = l2.next

        return dummy.next

#本方法时间复杂度为“O(max(m, n))”，其中m = l1 的长度，n = l2 的长度

# 作者：Shawxing精讲算法
# 链接：https://leetcode.cn/problems/add-two-numbers/solutions/2826226/jiang-lian-biao-fan- guo-lai-kan-jiu-bu-b-mfhh/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

注意

返回一个表示和的链表

考点

链表遍历 + 进位处理

哑巴节点

“哑巴节点”（Dummy Node），在算法中更常见的叫法是“虚拟头节点”或“哨兵节点”。

顾名思义，它就像一个“哑巴”，它本身不存储任何有效的数据（通常初始化为 0 或 null），它的存在仅仅是为了占位，充当整个链表的“假头”。

为什么需要哑巴节点？

在链表操作中，如果没有哑巴节点，我们在处理链表的第一个节点时，往往需要写很多 if-else 来判断“这到底是不是第一个节点”。有了哑巴节点后，所有的节点（包括真正的第一个节点）都有了前驱节点，从而统一了操作逻辑，大大简化了代码。

3.无重复字符的最长子串

答案

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: 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

        

知识点

滑动窗口+set

set

• 在 Python 中，set 是一种无序且不包含重复元素的数据结构。
• 它最大的特点是：查找速度极快。判断一个元素是否在集合中（例如 if 'a' in lookup:），平均时间复杂度是 O(1)。相比之下，如果你用列表（List）来存，查找需要遍历整个列表，速度是 O(N)。
• set（集合）：使用的是 .add() 方法来添加元素。
• list（列表）：使用的才是 .append() 方法来追加元素。
• 元组：天生不可变，不能直接添加。
• 字典：使用update添加元素

  d = {'name': 'Alice'}
  d.update({'age': 25, 'city': 'Beijing'})
  print(d)            # 输出: {'name': 'Alice', 'age': 25, 'city': 'Beijing'}

4.寻找两个正序数组的中位数

答案

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        if len(nums1) > len(nums2):
            return self.findMedianSortedArrays(nums2, nums1) # 必须交换避免后面 mid2 为负数
        m, n = len(nums1), len(nums2)
        k = (m + n + 1) // 2
        left = 0
        right = m
        while left <= right:
            mid1 = (left + right) // 2  # 表示放在左边 nums1 的个数
            mid2 = k - mid1  # 表示放在左边 nums2 的个数
            l1 = nums1[mid1 - 1] if mid1 > 0 else float('-inf')
            r1 = nums1[mid1] if mid1 < m else float('inf') 
            l2 = nums2[mid2 - 1] if mid2 > 0 else float('-inf')
            r2 = nums2[mid2] if mid2 < n else float('inf')
            if l1 <= r2 and l2 <= r1:
                if (m + n) % 2 == 0:
                    return (max(l1, l2) + min(r1, r2)) / 2.0
                else:
                    return max(l1, l2)
            elif l1 > r2:
                right = mid1 - 1
            else:
                left = mid1 + 1

5.最长回文子串

答案

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

        n = len(s)
        ans_left = ans_right = 0

        for i in range(2 * n - 1):
            l, r = i // 2, (i + 1) // 2
            while l >= 0 and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            # 循环结束后，s[l+1] 到 s[r-1] 是回文串
            if r - l - 1 > ans_right - ans_left:
                ans_left, ans_right = l + 1, r  # 左闭右开区间

        return s[ans_left: ans_right]

考点

中心扩展法，也就是：每一个回文串都有一个“中心”，从中心向左右两边扩展，只要左右字符相等，就继续扩展。

注意

python切片是左闭右开

输出的是 s 中最长的 回文 子串