数组与字符串基础操作
深度解析 ↓💡 数组是一段连续内存上的随机访问容器，字符串是「字符序列 + 文本语义」的封装；前者的灵魂是 O(1) 按下标寻址，后者的坑多来自各语言的编码与可变性差异。
核心要点
- 数组连续存储，按下标访问是 O(1)
- 动态数组尾部追加均摊 O(1)，中间插删 O(n)
- 二维网格在 C 系语言中按行主序存储，用方向数组统一邻居遍历（详见 B1）
- 字符串可变性：C++/Rust 可变，Python
str不可变 - Rust
str是 UTF-8，索引是字节不是字符 - 循环内拼接字符串易退化为 O(n²)，应缓冲后合并（详见 B2）
复杂度速查
| 操作 / 场景 | 时间 | 空间 | 说明 |
|---|---|---|---|
按下标访问 a[i] | O(1) | O(1) | 连续内存，地址 = base + i×size |
| 动态数组尾部追加 | 均摊 O(1) | O(1) | 扩容单次 O(n)，均摊后 O(1) |
| 中间插入 / 删除 | O(n) | O(1) | 需搬移后续元素 |
| 线性遍历 | O(n) | O(1) | 逐元素访问 |
| 二维网格全遍历 | O(m·n) | O(1) | m 行 n 列 |
| 朴素子串查找 | O(n·m) | O(1) | 更快的 KMP 为 O(n+m) |
| 原地反转 | O(n) | O(1) | 双指针对撞交换 |
模板代码
模板 1：方向数组遍历二维网格用偏移数组统一处理 4/8 邻域，消除重复的分支判断。
# 4 向：上 下 左 右；8 向：再含对角线
DIR4 = [(-1, 0), (1, 0), (0, -1), (0, 1)]
DIR8 = [(-1, -1), (-1, 0), (-1, 1), (0, -1),
(0, 1), (1, -1), (1, 0), (1, 1)]
def neighbors(grid, r, c, diagonal=False):
"""返回网格中 (r, c) 的所有合法邻居坐标"""
if not grid: # 空网格守卫，避免 grid[0] 越界
return []
rows, cols = len(grid), len(grid[0])
res = []
for dr, dc in (DIR8 if diagonal else DIR4):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
res.append((nr, nc))
return res模板 2：字符串分割、拼接与数值转换安全的「切分 → 逐段处理 → 合并」范式，避免 O(n²) 拼接。注意三语言对非法段的容错语义并不一致——Rust 版用
unwrap_or(0) 静默归零，C++ stoll 抛 std::invalid_argument，Python int() 抛 ValueError；如需统一行为，应显式选择「静默跳过」或「遇错报错」策略。def parse_ints(s: str) -> list:
"""把逗号分隔的整数字符串解析为整数列表（非法段抛 ValueError）"""
return [int(t) for t in s.split(',') if t.strip()]
def join_ints(v) -> str:
"""把整数列表合并为逗号分隔字符串（O(n) 拼接）"""
return ','.join(str(x) for x in v)模板 3：原地删除元素（快慢指针雏形）O(n) 时间、O(1) 额外空间地移除满足条件的元素，并返回新长度。
def remove_element(nums: list, val: int) -> int:
"""原地移除所有等于 val 的元素，返回新长度"""
k = 0
for i in range(len(nums)):
if nums[i] != val:
nums[k] = nums[i]
k += 1
return k模板 4：原地反转（数组 / 字符串）数组用双指针对撞交换做到 O(n) 时间、O(1) 额外空间；字符串因可变性与编码差异，三语言做法不同——反转不能在字节层面随意进行（详见 A5）。
def reverse_list(nums: list) -> None:
"""数组原地反转：双指针对撞，O(1) 额外空间"""
i, j = 0, len(nums) - 1
while i < j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
def reverse_string(s: str) -> str:
"""str 不可变，无法原地反转，返回新串（等价于切片 s[::-1]）"""
return ''.join(reversed(s))易错点
- 越界（off-by-one）：
a[n]、s[len(s)]是最常见的错误；当上界是长度时循环条件应写< n而非<= n，多语言中越界后果不同（C++ 未定义行为、Rust panic、Python 抛IndexError）。 - Rust 字符串索引是字节：
s[i]直接编译不通过；&s[i..j]是字节切片且端点必须落在 UTF-8 字符边界上，否则运行时 panic；要取「第 i 个字符」应s.chars().nth(i)或先collect::<Vec<char>>()。 - 字符串反转不能按字节：C++
std::string与 Rust 字节容器按字节反转会把多字节 UTF-8 码点翻面成非法序列（呼应上一条「Rust 字符串索引是字节」）；Rust 的安全写法是s.chars().rev().collect::<String>()（产生新串、O(n) 分配），Python 用''.join(reversed(s))，需要真·原地反转时只能对纯 ASCII 的字节数组操作。 - C++
size_t无符号陷阱：真正会出问题的是索引变量保持无符号的写法for (size_t i = v.size() - 1; i >= 0; --i)——v为空时v.size() - 1在无符号域下溢为SIZE_MAX，而i >= 0对无符号恒真，循环便越界访问或永不结束。修复：先把上界转为有符号再比较，for (int i = (int)v.size() - 1; i >= 0; --i)；或改用反向迭代器for (auto it = v.rbegin(); it != v.rend(); ++it)。反过来，若写成for (int i = v.size() - 1; i >= 0; --i)，v.size() - 1同样在无符号域下溢，但赋给int后的结果依赖实现（常见平台截断为 -1，循环体不执行、并不越界）——因此不能指望这种「顺手转型」来规避下溢，应显式转型。 - Python 循环内拼接字符串：
s += t每次产生新对象，累积是 O(n²)；应parts.append(t)后''.join(parts)。 - 二维数组初始化别名：
[[0] * n] * m得到的是同一行的 m 个引用，改一行会波及所有行；应写[[0] * n for _ in range(m)]。 - 扩容导致失效：C++
push_back触发扩容会使全部迭代器/引用失效，Rust 在借用未结束时不能可变修改Vec，遍历中扩容需特别当心。