数组与字符串基础操作
深度解析 ↓💡 数组是一段连续内存上的随机访问容器，字符串是「字符序列 + 文本语义」的封装；前者的灵魂是 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 邻域，消除重复的分支判断。
/// 返回网格中 (r, c) 的所有合法邻居坐标
fn neighbors(grid: &[Vec<i32>], r: usize, c: usize, dirs: &[(i32, i32)]) -> Vec<(usize, usize)> {
if grid.is_empty() { return Vec::new(); }
let (rows, cols) = (grid.len() as i32, grid[0].len() as i32);
let mut res = Vec::new();
for &(dr, dc) in dirs {
let (nr, nc) = (r as i32 + dr, c as i32 + dc);
if nr >= 0 && nr < rows && nc >= 0 && nc < cols {
res.push((nr as usize, nc as usize));
}
}
res
}
// 4 向：上下左右；8 向：再含四条对角线
const DIR4: [(i32, i32); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];
const DIR8: [(i32, i32); 8] = [
(-1, 0), (1, 0), (0, -1), (0, 1),
(-1, -1), (-1, 1), (1, -1), (1, 1),
];模板 2：字符串分割、拼接与数值转换安全的「切分 → 逐段处理 → 合并」范式，避免 O(n²) 拼接。注意三语言对非法段的容错语义并不一致——Rust 版用
unwrap_or(0) 静默归零，C++ stoll 抛 std::invalid_argument，Python int() 抛 ValueError；如需统一行为，应显式选择「静默跳过」或「遇错报错」策略。/// 把逗号分隔的整数字符串解析为整数向量（非法段静默归零）
fn parse_ints(s: &str) -> Vec<i64> {
s.split(',')
.map(str::trim)
.filter(|t| !t.is_empty())
.map(|t| t.parse::<i64>().unwrap_or(0))
.collect()
}
/// 把整数向量用逗号拼接为字符串（一次分配，O(n)）
fn join_ints(v: &[i64]) -> String {
v.iter().map(|x| x.to_string()).collect::<Vec<_>>().join(",")
}模板 3：原地删除元素（快慢指针雏形）O(n) 时间、O(1) 额外空间地移除满足条件的元素，并返回新长度。
/// 移除所有等于 val 的元素，返回新长度（原地覆盖，保持相对顺序）
fn remove_element(nums: &mut Vec<i32>, val: i32) -> usize {
let mut k = 0; // 慢指针：保留区间的下一个写入位置
for i in 0..nums.len() {
if nums[i] != val {
nums[k] = nums[i];
k += 1;
}
}
k
}模板 4：原地反转（数组 / 字符串）数组用双指针对撞交换做到 O(n) 时间、O(1) 额外空间；字符串因可变性与编码差异，三语言做法不同——反转不能在字节层面随意进行（详见 A5）。
/// 数组：双指针对撞交换，O(n) 时间 / O(1) 额外空间（等价于标准库 nums.reverse()）
fn reverse_array(nums: &mut [i32]) {
let (mut i, mut j) = (0usize, nums.len());
while i + 1 < j {
j -= 1;
nums.swap(i, j);
i += 1;
}
}
/// 字符串：返回反转后的**新串**（O(n) 额外分配）。
/// ⚠️ 不能对 String / &mut str 按字节原地反转：那会把多字节 UTF-8 码点逐字节翻面成非法序列。
/// 正确做法是按 char 反转后重新收集。
fn reverse_string(s: &str) -> String {
s.chars().rev().collect()
}
/// 真·原地反转只对「字节容器」成立，且**仅在内容为纯 ASCII 时安全**。
fn reverse_ascii_bytes(buf: &mut Vec<u8>) {
buf.reverse(); // 逐字节翻面；调用者须确保内容是 ASCII
}易错点
- 越界（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，遍历中扩容需特别当心。