想象一下，你在竞赛中遇到一个字符串匹配题，如果用暴力方法逐个比较字符，1000长度的串就会让你直接TLE。但如果你学会前缀和或KMP算法，同样的题目可能只需要O(n)时间就能解决。今天咱们就从最基础的数组与字符串操作说起，这些技巧就像信息学竞赛的"基本功"，用得越溜，越能节省宝贵的思考时间。
核心概念讲解
1. 数组
数组是连续内存存储的同类型数据集合，通过索引快速访问（时间复杂度O(1)）。
关键点：
int arr[n]：动态数组（C++98标准不支持，需用vector）arr[i]：第i个元素的值（下标从0开始）越界访问会导致UB（未定义行为），竞赛中常引发WA
图示：
内存布局：
[arr[0], arr[1], arr[2]] → 实际地址：base, base+4, base+8
2. 字符串
string类封装了字符数组，支持[]访问、.size()等方法。
注意：
C风格字符串
char str[]以\0结尾竞赛中
string比char*更安全，避免手动释放内存
3. 常用操作
遍历：
for(int i=0; i<n; i++)子串提取：
s.substr(pos,len)查找：
find()返回位置（找不到返回string::npos）
C++代码示例
#include <bits/stdc++.h>
using namespace std;
// 1. 统计字符串中元音字母数量
void countVowels() {
string s = "Hello World!";
int cnt = 0;
for(char c : s) { // 范围for简化遍历
if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') cnt++;
}
cout << "元音数量: " << cnt << endl; // 输出3
}
// 2. 二维数组转置（矩阵转置）
void transposeMatrix(vector<vector<int>>& mat) {
int n = mat.size();
vector<vector<int>> trans(n, vector<int>(n));
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
trans[j][i] = mat[i][j]; // 行列交换
}
// 3. 字符串反转（双指针法）
void reverseString(string &s) {
int l=0, r=s.size()-1;
while(l<r) swap(s[l++], s[r--]);
}
int main() {
countVowels(); // 测试函数
vector<vector<int>> mat = {{1,2},{3,4}};
transposeMatrix(mat); // 输出{{1,3},{2,4}}
string str = "abc";
reverseString(str);
cout << str; // cba
return 0;
}
算法分析
| 操作 | 时间复杂度 | 空间复杂度 |
|—————|—————–|————|
| 数组遍历 | O(n) | O(1) |
| 字符串查找 | O(n) (朴素算法) | O(1) |
| 二维矩阵转置 | O(n²) | O(n²) |
适用场景：
需要频繁随机访问时用数组（如前缀和预处理）
字符串处理优先用
string而非C风格字符串
局限性：
- 静态数组大小固定，动态扩容需谨慎（
vector更灵活）
经典例题
- P1617 字符串匹配（洛谷）
题目描述：给定模式串和文本串，统计出现次数。
思路：先实现暴力匹配（O(mn)），再尝试优化（如KMP算法）。
- CF151B Beautiful Year（AtCoder）
题目描述：找出最小的大于给定年份且各位数字不重复的年份。
关键：将年份转为字符串处理，逐位检查。
推荐练习
（掌握next数组的构建，为后续学习打基础）
（需要综合运用字符串哈希和前缀和）
（进阶：结合数组和字符串处理）
小结
今天你学会了：数组的高效访问、string的基本操作，以及如何通过这些技巧简化问题。记住，好代码不是写出来的，是改出来的——多动手调试，下次遇到字符串题，试试用find()代替循环！
下期预告：字符串哈希技术——让"字符串相等判断"从O(n)变成O(1)，敬请期待！