数组与字符串基础操作
深度解析 ↓💡 数组是一段连续内存上的随机访问容器，字符串是「字符序列 + 文本语义」的封装；前者的灵魂是 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 邻域，消除重复的分支判断。
#include <utility>
#include <vector>
// 方向数组：4 向（上下左右）与 8 向（含对角线）
const int dx4[4] = {-1, 1, 0, 0};
const int dy4[4] = {0, 0, -1, 1};
const int dx8[8] = {-1, 1, 0, 0, -1, -1, 1, 1};
const int dy8[8] = {0, 0, -1, 1, -1, 1, -1, 1};
// 收集 (r, c) 的合法邻居坐标
std::vector<std::pair<int, int>> neighbors(const std::vector<std::vector<int>>& g, int r, int c, bool diagonal) {
if (g.empty()) return {}; // 空网格守卫，避免 g[0] 越界
int m = (int)g.size(), n = (int)g[0].size();
const int* dx = diagonal ? dx8 : dx4;
const int* dy = diagonal ? dy8 : dy4;
int k = diagonal ? 8 : 4;
std::vector<std::pair<int, int>> res;
for (int i = 0; i < k; ++i) {
int nr = r + dx[i], nc = c + dy[i];
if (nr >= 0 && nr < m && nc >= 0 && nc < n)
res.push_back({nr, nc});
}
return res;
}模板 2：字符串分割、拼接与数值转换安全的「切分 → 逐段处理 → 合并」范式，避免 O(n²) 拼接。注意三语言对非法段的容错语义并不一致——Rust 版用
unwrap_or(0) 静默归零，C++ stoll 抛 std::invalid_argument，Python int() 抛 ValueError；如需统一行为，应显式选择「静默跳过」或「遇错报错」策略。#include <cstddef>
#include <sstream>
#include <string>
#include <vector>
// 按分隔符切分字符串（跳过空段）
std::vector<std::string> split(const std::string& s, char delim) {
std::vector<std::string> res;
std::istringstream iss(s);
std::string cur;
while (std::getline(iss, cur, delim))
if (!cur.empty()) res.push_back(cur);
return res;
}
// 段内字符串转整数；非法段会抛 std::invalid_argument
std::vector<long long> parseInts(const std::string& s, char delim = ',') {
std::vector<long long> res;
for (const std::string& t : split(s, delim))
res.push_back(std::stoll(t));
return res;
}
std::string joinInts(const std::vector<long long>& v, char delim = ',') {
std::ostringstream oss;
for (size_t i = 0; i < v.size(); ++i) {
if (i) oss << delim;
oss << v[i];
}
return oss.str();
}模板 3：原地删除元素（快慢指针雏形）O(n) 时间、O(1) 额外空间地移除满足条件的元素，并返回新长度。
#include <vector>
// 移除所有等于 val 的元素，返回新长度
int removeElement(std::vector<int>& nums, int val) {
int k = 0; // 慢指针：保留区间的下一个写入位置
for (int i = 0; i < (int)nums.size(); ++i)
if (nums[i] != val)
nums[k++] = nums[i];
return k;
}模板 4：原地反转（数组 / 字符串）数组用双指针对撞交换做到 O(n) 时间、O(1) 额外空间；字符串因可变性与编码差异，三语言做法不同——反转不能在字节层面随意进行（详见 A5）。
#include <string>
#include <utility>
#include <vector>
// 一、数组：双指针对撞交换（对应标准库 reverse(nums.begin(), nums.end())）
void reverseArray(std::vector<int>& nums) {
for (int i = 0, j = (int)nums.size() - 1; i < j; ++i, --j)
std::swap(nums[i], nums[j]);
}
// 二、字符串：std::string 可变且连续，可按字符级对撞交换（等价 reverse(s.begin(), s.end())）
void reverseString(std::string& s) {
for (int i = 0, j = (int)s.size() - 1; i < j; ++i, --j)
std::swap(s[i], s[j]);
}
// ⚠️ std::string 的反转是「字节级」的：对纯 ASCII 安全；
// 含多字节 UTF-8 时会把码点切断成非法序列，需先按码点切分再反转。易错点
- 越界（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，遍历中扩容需特别当心。