1. 为什么数组是算法训练的第一课它的地位和底层逻辑很多刚进训练营的同学问我第一天就讲数组是不是太简单了说实话我当年带第一届训练营的时候也这么想过直到后来发现一个残酷的事实——数组题做不好的人后面学链表、树、动态规划全都磕磕绊绊。原因很简单数组是所有数据结构里最接近硬件存储模型的一种你如果连数组的存取逻辑都没吃透后面理解LRU Cache这种基于哈希表链表的东西就是空中楼阁。先摆一个结论数组在算法里不是入门玩具而是地基。你可以不懂红黑树、不懂AVL但你不可能绕开数组去写任何一段像样的业务代码。职场里最常见的算法场景比如分页、去重、排序、聚合统计、区间汇总底层全是数组操作。你去看各大厂面试题哪怕挂在链表、树、图的名下最终落地还是要靠数组来存储和索引节点。所以第一天把数组掰开揉碎收益是长期复利式的。数组为什么重要根子在于它和内存的关系。现代计算机的内存是一段连续编址的线性空间从地址0x00到0xFF...每个字节都有自己的门牌号。数组就是直接在这段连续空间里划一块区域按顺序摆数据。你声明int arr[5]编译器会帮你申请5 * sizeof(int)字节的连续空间arr[0]占据最低地址arr[4]占据最高地址。这听起来平平无奇但它是数组一切性能优势的源头。这种连续内存模型带来两个核心性质很多同学到毕业都不见得真正理解性质一随机访问的时间复杂度是 O(1)。因为底层知道首地址base要访问下标i只需要做一次加法base i * sizeof(元素类型)。CPU 直接就能算出目标地址不需要遍历任何东西。这就是为什么数组查询极快也是为什么面试官总爱问数组和链表的区别核心差异就在这。性质二插入和删除必须搬移数据。因为数组要求连续你在中间挖掉一个坑后面的元素必须整体前移把坑填上在中间插一个元素后面的必须整体后移腾位置。这个搬移操作的成本是 O(n)。很多新手不理解为什么数组插入慢其实就是在内存里做了一次批量 memmove。关于第一天的训练我建议你先在自己电脑上写一段探针代码打印出数组元素的内存地址感受一下连续到底长什么样。下面是我常用的一段 C 语言示例#include stdio.h int main() { int arr[5] {10, 20, 30, 40, 50}; for (int i 0; i 5; i) { printf(arr[%d] %d, address %p\n, i, arr[i], arr[i]); } return 0; }你运行后会看到地址是递增的相邻元素之间相差4个字节因为 int 占 4 字节。我见过太多人只是知道数组是连续的但从没亲眼看一眼那个递增的地址这种直觉上的缺失会在你做二分查找边界、二维数组索引换算时反复坑你。2. 从数组的增删改查随机访问的甜头与搬移的代价2.1 增删改查每一招的时间复杂度数组的基本操作就四类增、删、改、查。每一类的复杂度都不一样先看表格操作时间复杂度前提条件说明随机访问arr[i]O(1)知道下标直接地址计算按值查找O(n)无序数组必须逐个比较按值查找O(log n)有序数组配合二分查找尾部插入/删除O(1)容量够/不用保持顺序只在末尾操作中间插入/删除O(n)无后续元素搬移修改arr[i]O(1)知道下标直接写内存这里有个常见的认知误区提到数组查找很多回答说数组查找是 O(1)。严格说随机访问是 O(1)按值查找是 O(n)。只有在有序前提下你才能通过二分把查找降到 O(log n)但二分本身又是一个高频考点我会在后面章节单讲它的边界细节。2.2 插入和删除为什么必须搬移以及什么时候可以不搬数组在中间插入的机制我用一句话概括腾位置。假设数组是[1, 2, 3, 4, 5]要在下标 2 的位置插入99步骤是检查容量是否够不够就得扩容后面讲动态数组时会展开从末尾开始把5移到下标 44移到下标 33移到下标 2... 注意必须从后往前搬如果你从头往后搬数据会被覆盖掉下标 2 空出来后写入99。同理删除下标 2 的元素时要从3开始从前往后搬3移到下标 24移到下标 35移到下标 4末尾置零或不管。这两句从后往前从前往后看起来是细节但我在实际评审代码时见过太多人写错方向导致数据错乱。还有一个优化点很多老手才知道如果题目不要求保持元素相对顺序删除中间元素时可以不搬移全量。具体做法是把最后一个元素复制到要删除的位置然后把size减一。这样删除从 O(n) 降到 O(1)。这个技巧在数组去重移除元素这类 LeetCode 题里经常能用上就是经典的快慢指针覆盖思路。2.3 初始化与越界两个让你的程序莫名其妙的凶手热搜词里有人搜数组初始化c字符串数组初始化说明初始化是新手高频困惑点。这里分语言讲一下C 语言没初始化的局部数组里面是乱值栈上残留数据全局数组默认全 0。所以 C 程序员写int arr[5];后直接读结果是不可预测的。C如果写vectorint v(5)默认会初始化为 0但原生数组int arr[5]仍然和 C 一样是乱值。Java的int[] arr new int[5]默认全 0但Integer[]这种包装类数组默认是null。Python的list本身就是动态数组写[0] * 5得到 5 个 0。这些初始化细节看似琐碎实际写算法题时如果你不清空状态数组上一次运行的数据会污染下一次结果。我在训练营见过一个同学调试回溯算法反复出现诡异结果最后发现是全局状态数组没在递归入口重置。越界是另一个经典杀手。C/C 的数组越界是未定义行为不会直接报错可能覆盖了其他变量导致明明没改这个变量它却变成了奇怪的值。有一次我帮学生排查 bug发现他for循环里写i n把数组最后一个元素之后的垃圾值读出来当成合法数据程序行为完全随机。后来的习惯是涉及数组下标的地方永远用size变量而不是写死常量循环条件里能写成 size就不要写成 size。3. 双指针与滑动窗口数组题最常用的两类破局思路第一天训练如果只做读、写、遍历那确实太简单。真正拉开差距的是基于数组的双指针和滑动窗口。这两类技巧覆盖了 LeetCode 上大量数组题的解法训练营第一天我就会带学员把它们过一遍。3.1 双指针一快一慢一左一右双指针的核心思想是通过维护两个下标来减少不必要的遍历次数。最经典的三个形态左右指针左指针left从最左边出发右指针right从最右边出发相向而行。典型应用是两数之和有序数组如果arr[left] arr[right] target说明右边太大右指针左移如果 target说明左边太小左指针右移。整个过程在一次遍历内完成复杂度从暴力 O(n²) 降到 O(n)而且不需要额外空间。快慢指针一个指针走得快一个走得慢。典型应用是移除指定元素或数组去重。核心逻辑是维护一个slow指针表示有效区的边界fast指针负责探路。当fast遇到一个合法值就赋值给slow位置并把slow前进一位遇到不合法的值slow原地不动fast继续向前。这样一轮下来前半段全部是合法数据后半段是废弃数据整体复杂度 O(n)。同向并行指针两个指针都从头开始但移动节奏不同步常用于合并两个有序数组。这题面试出现频率极高核心坑点是从后往前填避免覆盖未处理的元素。我面试候选人的时候就常拿这道题考察边界意识能一次写对的人不到三成。为了让你直观理解双指针的价值我写一段快慢指针去重的 C 示例#include vector #include iostream int removeDuplicates(std::vectorint nums) { if (nums.empty()) return 0; int slow 0; for (int fast 1; fast nums.size(); fast) { if (nums[fast] ! nums[slow]) { slow; nums[slow] nums[fast]; } } return slow 1; // 有效长度 } int main() { std::vectorint nums {0, 0, 1, 1, 1, 2, 2, 3, 3, 4}; int len removeDuplicates(nums); std::cout len len std::endl; for (int i 0; i len; i) { std::cout nums[i] ; } std::cout std::endl; return 0; }输出结果是len 5数组前五个元素变成0 1 2 3 4。你注意看slow指向的位置它始终是下一个合法写入位而fast负责向前打探这就是快慢指针的精髓。3.2 滑动窗口把连续子数组问题变成移动区间问题滑动窗口处理的典型问题是在一个数组里找满足某个条件的连续子数组/子串比如和大于等于 target 的最短子数组无重复字符的最长子串。暴力的做法是枚举所有起点和终点复杂度 O(n²)滑动窗口把复杂度降到 O(n)原理是让窗口右边界不断扩张左边界按需收缩全程每个元素最多进出窗口一次。我以一个很常见的题目长度最小的子数组为例来说明算法逻辑给定一个包含n个正整数的数组和一个正整数target找出该数组中满足其和 target的长度最小的连续子数组并返回其长度。如果不存在返回 0。解题步骤定义left 0表示窗口左边界sum 0表示当前窗口内元素之和result INT_MAX用于记录最短长度。用right从 0 遍历数组每轮把nums[right]累加到sum这是窗口右边界扩张。当sum target时进入内层while循环先记录当前窗口长度right - left 1更新result然后把nums[left]从sum中减去left窗口左边界收缩。内层循环重复直到sum target右边界继续前进。遍历结束如果result仍是INT_MAX说明不存在满足条件的子数组返回 0否则返回result。这里有一个新手特别容易踩的坑内层while条件为什么要用而不是因为当sum已经超过target时不断收缩左边界可以继续寻找更短的满足条件子数组。如果你只在sum target时记录就会漏掉大于 target 也能满足条件的情况。3.3 数组里的子集和难题暴力枚举的边界在哪热搜词里有一句很典型的话已知固定数值如何确定数组中的哪些数据和等于固定值。这其实是子集和问题Subset Sum它的完整版是 NP 完全的但给定限制条件时可以优化。先说最简单的暴力枚举。如果数组长度n不大比如n 20可以用二进制枚举把每个元素看成选/不选两种状态用0 ~ (1 n) - 1的每个整数对应一种组合。i的第k位是 1 表示选中第k个元素。伪代码如下for (int mask 0; mask (1 n); mask) { int sum 0; for (int k 0; k n; k) { if (mask (1 k)) sum arr[k]; } if (sum target) { // 找到一组解 } }复杂度是 O(n * 2^n)n20时是两千多万次勉强可接受n30以上就爆了。如果你真的遇到n40这类中等规模可以用折半枚举meet in the middle把数组分成两半分别枚举两半所有子集和然后排序二分匹配。这样复杂度从 O(2^n) 降到 O(2^(n/2) * n)n40也能跑。这个技巧属于进阶内容但我觉得值得在第一天就提一嘴因为太多人一看到题就上暴力循环根本不知道有更优解。4. 二维数组与矩阵问题下标换算、遍历方向与环形队列4.1 二维数组到底怎么存储的行优先和列优先二维数组在逻辑上是表格但在内存里依然是线性的。C/C 采用行优先存储也就是先把第一行铺满再铺第二行。arr[i][j]的地址换算公式是address base (i * 列数 j) * sizeof(元素类型)这个公式你必须烂熟于心。面试题里经常出现把二维数组按行优先展开成一维让你反过来做索引映射这就是i * cols j的直接应用。Python 里没有真正的原生二维数组一般用列表的列表[[0] * cols for _ in range(rows)]模拟。这里有个经典陷阱[[0] * cols] * rows看似生成了二维数组实际上每一行都是同一个列表对象的引用改一个元素会波及其他行。训练营里几乎每年都有人踩这个坑你如果写 Python务必用第一种写法。4.2 遍历边界螺旋矩阵、对角线遍历的规律总结二维数组的遍历题很大程度上考验的是方向控制和边界判断。螺旋矩阵是最典型的一道题按顺时针方向从外到内遍历所有元素。核心思路是维护四个边界top, bottom, left, right每走完一条边就收缩对应边界直到上下边界交错或左右边界交错。int top 0, bottom rows - 1, left 0, right cols - 1; while (top bottom left right) { // 从左到右遍历 top 行 for (int j left; j right; j) process(matrix[top][j]); top; // 从上到下遍历 right 列 for (int i top; i bottom; i) process(matrix[i][right]); right--; // 从右到左遍历 bottom 行注意防止重复 if (top bottom) { for (int j right; j left; j--) process(matrix[bottom][j]); bottom--; } // 从下到上遍历 left 列 if (left right) { for (int i bottom; i top; i--) process(matrix[i][left]); left; } }代码里那两个if判断特别关键。遍历完第一条边后top和right已经改变了如果此时top bottom或left right说明矩阵已经全部遍历完再走第三条边就是重复访问。很多初学者死记这套代码却不理解这两个if的防御意义一旦矩阵是 1 行或 1 列的边界情况立刻出 bug。对角线遍历之字形遍历是另一个高频题它考察的是方向切换规律当下标越界时需要同时调整行和列的方向。我不建议死记公式更推荐的做法是分四种情况处理向右上方走、向左下方走、撞到右边界、撞到下边界。把每种情况的坐标变化写清楚代码再长也不容易错。4.3 环形队列数组模拟循环结构的经典思路热搜词里有句描述我一看就知道出自哪道经典题假设以数组 q[m] 存放循环队列中的元素同时以 rear 和 length 分别指示环形队列中的队尾和长度。这是数据结构教科书里的循环队列实现算法训练营第一天讲数组时经常会捎带提它因为它充分体现了数组下标取模的思想。循环队列存在的意义是复用数组空间。普通队列用数组实现时出队后头指针前进前面的空间就浪费了。循环队列把数组首尾相连当rear走到m-1后再入队rear (rear 1) % m就回到了 0。用rear和length两个变量实现时判空条件是length 0判满是length m。队头位置怎么求答案是(rear - length m) % m。这个取模公式非常容易写错如果你直接写(rear - length) % m当rear - length是负数时大多数编程语言的取模结果也是负数下标就非法了。所以加上一个 m 再取模是标准写法。我第一次写循环队列时就在这卡了半小时后来形成肌肉记忆凡涉及下标回绕一律写成(index m) % m的格式。5. 字符串本质是字符数组数组方法和双指针的直接应用5.1 字符数组与字符串的区别终止符的边界热搜词里有人搜c字符串数组初始化指针数组存放字符串说明字符数组和字符串的关系是个高频困惑点。在 C 语言里字符串就是一个以\0结尾的字符数组。char str[] hello实际占 6 个字节最后一个字节是\0。很多缓冲区溢出漏洞的根源就是忘记给\0留位置比如char buf[5]; strcpy(buf, hello);直接越界。在 C 里std::string封装了动态字符数组c_str()方法返回的指针依然是以\0结尾的字符数组。在 Java 里String是不可变对象底层是char[]但你不能原地修改想修改就得转成char[]或StringBuilder。Python 的str也是不可变的转列表list(s)后元素是每个字符修改后再.join(...)拼回来。5.2 数组转字符串不同语言的姿势与踩坑数组转字符串在热搜里也是一条可能因为各语言 API 太多容易记混。Python 里对字符串列表用,.join(list)对数字列表得先map(str, list)再 join。C 里可以用std::to_string逐个拼接或者用stringstream。Java 里Arrays.toString(arr)返回带方括号的形式如果你只要逗号分隔可以借助String.join(,, arr)Java 8。JavaScript 里直接用arr.join(,)最简单。有个非常隐蔽的坑JavaScript 的arr.join()如果不传参数默认用逗号分隔但如果数组元素中本身含逗号结果会变得难以解析。所以做数据拼接时永远明确指定分隔符。5.3 字符处理实战过滤、分割、去重一锅端我拿一个热搜里提到的需求来演示数组分割并显示包含某一字符。这个需求在日志分析、关键词筛选里很常见。假设你有一个字符串数组想过滤出包含子串abc的所有元素并按逗号拼接展示Python 代码是这样data [hello-abc, world, xabcx, plain] filtered [s for s in data if abc in s] print(,.join(filtered)) # 输出 hello-abc,xabcx一行列表推导式就解决了。这在算法题里对应的是字符串匹配过滤如果是少量数据直接暴力in判断即可如果数据量极大就需要引入 KMP、AC 自动机这类模式匹配算法。热搜词里也出现KMP 算法这里先不展开但你至少要有什么规模用什么方案的判断力。5.4 反转字符串、判断回文双指针在字符串数组上的练习反转一个字符串最简单的方式是转成字符数组后用左右指针交换void reverseString(char* s, int sSize) { int left 0, right sSize - 1; while (left right) { char tmp s[left]; s[left] s[right]; s[right] tmp; left; right--; } }判断回文串的思路类似左右指针逐字符比较一旦不等就返回 false。进一步升级版是最多删除一个字符能否构成回文这题需要你在遇到不等时分别尝试删左边或删右边属于双指针的进阶用法。第一天训练如果把这两题做熟你对指针移动 边界终止的感知会强很多。6. 从静态数组到动态数组扩容机制、均摊分析与选择策略6.1 为什么需要动态数组固定长度的尴尬C 语言原生的int arr[100]是静态的长度一旦定下就不能改。实际业务里数据量往往不是你预先能决定的可能刚开始只有 10 条数据后来涨到 10 万条。你开小了不够用开大了浪费内存。于是就有了动态数组——最典型的就是 C 的std::vector、Java 的ArrayList、Python 的list。它们内部本质还是数组但支持在容量不足时自动扩容。6.2 扩容的均摊复杂度为什么 O(1) 和 O(n) 可以共存动态数组的容量是分阶梯增长的。以std::vector为例很多实现的扩容因子是 2当前容量为cap元素个数达到cap时申请2 * cap的新空间把旧数据全部拷贝过去释放旧空间容量翻倍。单看某一次扩容成本是 O(n)拷贝 n 个元素。但如果你把整个过程摊开看每次扩容后容量翻倍意味着下一次扩容要等再插入 n 个元素。把每次扩容的拷贝成本均摊到每个插入操作上每个插入操作的代价其实是 O(1)。这就是**均摊分析Amortized Analysis**的基础思想。面试官问vector 的 push_back 时间复杂度是多少正确答案就是均摊 O(1)单次可能 O(n)。这个思想特别重要训练营里很多同学觉得均摊这个词玄乎我举一个生活例子你每个月交房租是固定支出但每两年要大修一次水管花一笔巨款。把大修费用平均到每个月里你就知道自己长期现金流大概是稳定的。扩容就是这个大修平摊到每次插入后插入的平均成本仍然可接受。6.3 数组 vs 链表的选型一个被忽略的判断标准训练营第一天我会让学员做一个对比表格把数组和链表从内存、访问、插入删除、缓存友好性几个维度列清楚维度数组含动态数组链表内存布局连续分散节点间用指针连接随机访问O(1)O(n)插入/删除已知位置O(n)需搬移O(1)改指针CPU 缓存友好性好局部性原理差跳来跳去额外内存少只需数据本身多每个节点要存指针实际工程中很多时候链表并不比数组快。因为 CPU 对连续内存的缓存命中率很高数组遍历极快链表节点在内存里到处乱放每次访问都可能缓存未命中性能反而更差。插入删除链表更快只在已定位节点的前提下成立而定位节点本身往往需要 O(n) 的遍历这笔账要算总账。所以我的建议是默认选数组除非你有明确的理由需要频繁在中间插入删除且经常要扩容。这个建议可能和一些教科书给读者的印象相悖但我在实际项目里压测过很多次结论稳定。7. 数组题最容易翻车的地方我的调试经验和训练要点清单7.1 越界、空数组、单元素、溢出四类边界情况逐一排查训练营最后一天复盘时我最常说的一句话是你写的代码能过测试用例不代表能过隐藏用例。数组题最容易翻车的边界情况就那么几类每次写完代码我建议你按以下清单自测空数组len 0时你的循环会不会直接崩很多解法默认至少有一个元素没考虑空数组。单元素数组len 1时左右指针初始值会不会越界比如left 0, right len - 1 0循环条件left right不会进入这没问题但如果你在循环外直接访问arr[right 1]就炸了。双指针相遇二分查找和快慢指针都涉及left right的情况你到底处理没有整数溢出left right可能溢出 int 范围经典二分查找的mid left (right - left) / 2就是为了避免left right溢出。别小看这一行面试时写(left right) / 2会被面试官追问风险点。下标减一循环里用到i - 1时最常见的是i 0时访问arr[-1]。Java/C 里这是数组越界Python 里更坑——arr[-1]不报错返回的是最后一个元素逻辑完全错了但程序不崩排查起来非常痛苦。7.2 索引公式的推导习惯从暴力和推论两条路验证数组题里凡是出现i * cols j、(rear - length m) % m这类索引公式我都建议你推导 实例验证双保险。推导是指从定义出发自己推一遍地址换算实例验证是拿一个具体的二维数组比如 3 行 4 列手写几个坐标代入公式看看结果是否符合预期。举个真实案例有一次我帮一个学员看题他写了一个二维数组的斜线遍历行列坐标换算总是差 1。我让他把matrix[3][4]的每个元素按他的公式手算出来再与实际内存展开对比几分钟就找到错在哪一步——原来的公式把行优先当成了列优先。这比自己对着屏幕干瞪眼有效得多。7.3 今日训练清单从热身到强化的一周安排如果你今天刚开始练数组我按难度从低到高给一份清单你可以按自己的节奏分配到一周内完成热身实现数组的初始化、遍历、按值查找确认你能手写快慢指针去重的完整代码。基础巩固移除元素、移动零、合并两个有序数组。这三道题都是快慢指针或双指针的变体。进阶长度最小的子数组滑动窗口入门、螺旋矩阵二维数组边界处理、反转字符串中的单词字符串双指针综合。自我挑战和为 target 的所有子集先做n 20版本再尝试折半枚举思路。每个题目做完建议做两件事一是把题解思路用自然语言写一遍不看代码二是把时间复杂度和空间复杂度写在注释里。这两个习惯能帮你把会做变成真懂。7.4 语言差异提醒Python 的负索引、C 的迭代器失效、Java 的自动装箱最后再集中说一个实操层面的事不同语言处理数组时的细节差异直接决定你的 bug 率。Python 的负索引是双刃剑。方便归方便但如果你在调试时不小心把i-1写成了-1Python 不会告诉你越界而是悄悄返回最后一个元素这对算法验证是灾难。C 的vector有一个经典坑叫迭代器失效。当你对vector进行插入或删除操作后之前保存的迭代器可能全部失效继续使用就是未定义行为。比如在循环里边遍历边删除很容易踩中。Java 的ArrayList里存的是Integer对象不是原始int。当你在循环里大量读写时自动装箱int→Integer和拆箱Integer→int会产生额外对象这在算法竞赛或性能敏感场景下会拖慢速度。如果你要做纯数值计算int[]原生数组往往比ArrayListInteger快很多。我个人在实际使用中的体会是数组题的核心不在语法而在你脑海中是否有一个清晰的内存动画。每写一行代码都问自己三个问题——数据存在哪、下标指向哪、边界条件是什么。如果这三个问题都能即时回答你离数组题的举一反三就不远了。今天训练营第一天的内容能把这些基础动作变成肌肉记忆后续再学排序、二分、哈希表、动态规划都会轻松不少。第三天的二分查找专题我准备拿有序数组的边界处理做一次深度拆解到时候见。