数组与字符串

数组的本质

数组是一块连续的内存区域，每个元素占据固定大小的空间。这一物理特性决定了数组的一切操作特性。

给定数组首地址 base 和元素大小 size，访问下标 i 的元素地址 = base + i × size。这是一次乘法和加法，故时间复杂度 O(1)。

• 访问 arr[i]O(1) — 直接计算地址
• 搜索某值O(n) — 无序时需线性扫描；有序时可二分 O(log n)
• 插入（末尾）O(1) 摊还 — 动态数组；O(n) 最坏（扩容）
• 插入（中间）O(n) — 需移动后续所有元素
• 删除（末尾）O(1)
• 删除（中间）O(n) — 需移动后续所有元素

动态数组扩容机制

Python 的 list 是动态数组：初始分配少量容量，当元素数量超过容量时，申请约 1.125 倍（CPython 实现）的新空间并复制。

import sys

lst = []
prev_size = 0
for i in range(20):
    lst.append(i)
    curr = sys.getsizeof(lst)
    if curr != prev_size:
        print(f"长度 {i+1:2d}: 内存 {curr} 字节")
        prev_size = curr
# 输出类似: 长度 1: 88字节  长度 5: 120字节  长度 9: 184字节...
# 可见每隔若干次扩容一次

双指针技巧

双指针是用两个下标变量同时在数组上移动，避免暴力枚举 O(n²) 的经典技巧。分为两类：

对撞指针（头尾相向移动）

适用场景：有序数组、回文、两数之和等。

# 回文检测 — O(n) 时间，O(1) 空间
def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

# 有序数组两数之和 — O(n) 时间
def two_sum_sorted(nums: list, target: int) -> list:
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1   # 和太小，移动左指针增大和
        else:
            right -= 1  # 和太大，移动右指针减小和
    return []

快慢指针（同向不同速）

快指针每次走 2 步，慢指针每次走 1 步，用于检测环、找中点等。

# 移除数组中的重复元素（原地，不开额外空间）
def remove_duplicates(nums: list) -> int:
    if not nums: return 0
    slow = 0  # slow 指向已处理的最后位置
    for fast in range(1, len(nums)):   # fast 向前探路
        if nums[fast] != nums[slow]:    # 发现新元素
            slow += 1
            nums[slow] = nums[fast]     # 写入慢指针位置
    return slow + 1  # 新数组长度

滑动窗口

滑动窗口维护一个"窗口"区间 [left, right]，通过移动边界来枚举所有满足条件的子数组/子串，将 O(n²) 优化为 O(n)。

定长滑动窗口

# 长度为 k 的子数组最大和
def max_subarray_k(nums: list, k: int) -> int:
    window_sum = sum(nums[:k])       # 初始化第一个窗口
    max_sum = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]   # 移入新元素，移出旧元素
        max_sum = max(max_sum, window_sum)
    return max_sum  # O(n) 时间，O(1) 空间

可变长度滑动窗口

# 最长无重复子串 — LeetCode 3
def length_of_longest_substring(s: str) -> int:
    char_index = {}   # 记录每个字符最近出现的位置
    left = 0
    max_len = 0

    for right, ch in enumerate(s):
        if ch in char_index and char_index[ch] >= left:
            # 发现重复字符，收缩左边界到重复字符的下一位
            left = char_index[ch] + 1
        char_index[ch] = right         # 更新字符位置
        max_len = max(max_len, right - left + 1)

    return max_len
# 时间 O(n)，空间 O(min(m,n))，m 为字符集大小

# 示例
print(length_of_longest_substring("abcabcbb"))  # 3 ("abc")
print(length_of_longest_substring("pwwkew"))   # 3 ("wke")

前缀和

前缀和（Prefix Sum）是一种空间换时间的技巧：预处理 O(n)，之后每次区间查询 O(1)。

# 一维前缀和
def build_prefix(nums: list) -> list:
    n = len(nums)
    prefix = [0] * (n + 1)  # prefix[i] = nums[0..i-1] 之和
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    return prefix

# 区间 [left, right] 的和（O(1) 查询）
def range_sum(prefix: list, left: int, right: int) -> int:
    return prefix[right + 1] - prefix[left]

# 示例
nums = [1, 2, 3, 4, 5]
prefix = build_prefix(nums)
print(range_sum(prefix, 1, 3))  # 2+3+4 = 9
print(range_sum(prefix, 0, 4))  # 1+2+3+4+5 = 15

字符串算法

反转字符串

# Python 切片 O(n)，内置方法最简洁
s = "hello"
print(s[::-1])  # "olleh"

# 原地反转（字符数组）
def reverse_chars(arr: list) -> None:
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1; right -= 1

KMP 算法简介

暴力字符串匹配：O(n·m)。KMP 算法通过预计算"失配函数"（next 数组），避免重复比较，达到 O(n+m)。

def kmp_search(text: str, pattern: str) -> int:
    def build_next(p):
        # next[i] = pattern[0..i] 中最长真前缀 = 真后缀的长度
        nxt = [0] * len(p)
        j = 0
        for i in range(1, len(p)):
            while j > 0 and p[i] != p[j]:
                j = nxt[j - 1]
            if p[i] == p[j]:
                j += 1
            nxt[i] = j
        return nxt

    nxt = build_next(pattern)
    j = 0  # pattern 中已匹配的长度
    for i, ch in enumerate(text):
        while j > 0 and ch != pattern[j]:
            j = nxt[j - 1]  # 失配，利用 next 数组跳转
        if ch == pattern[j]:
            j += 1
        if j == len(pattern):
            return i - j + 1  # 找到，返回起始位置
    return -1

KMP 时间O(n + m) KMP 空间O(m)

经典题目详解

两数之和（哈希解法）

def two_sum(nums: list, target: int) -> list:
    seen = {}  # 值 → 下标
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]
        seen[x] = i  # 将当前元素存入哈希表
    return []
# 时间 O(n)，空间 O(n)

买卖股票最佳时机

def max_profit(prices: list) -> int:
    min_price = float('inf')
    max_profit = 0
    for price in prices:
        if price < min_price:
            min_price = price       # 更新历史最低价
        elif price - min_price > max_profit:
            max_profit = price - min_price  # 更新最大利润
    return max_profit
# 时间 O(n)，空间 O(1)  — 一次遍历，维护"历史最低价"