从大一开始刷题到现在工作三年我见过太多人学算法时在一个地方卡住——不是不懂思路而是不知道从哪儿下手。代码随想录算法训练营的Day01专门讲数组我当初跟着刷的时候感触很深因为数组虽然看起来简单但它在算法题里几乎是万能的“地基”。你后面学的链表、哈希表、字符串、滑动窗口底层全都有它的影子。今天这篇就针对训练营Day01的数组part01做个完整复盘从基础概念到底层实现再到经典题目的手写思路我会把每一步为什么这么做也一并讲清楚。无论你是刚入门的算法小白还是准备面试刷题的老手这篇应该都能给你一些实打实的参考。1. 数组到底是什么先把它彻底搞明白1.1 数组的内存结构与本质数组在算法题里看起来就是一个python nums [1, 2, 3, 4, 5]这么简单的结构但面试官考数组往往不是考你写for循环而是考你**对连续内存空间的理解**。 数组的底层本质是**一段连续的内存地址每个元素占用相同大小的空间**。这句话是理解一切数组操作的核心。因为内存是连续的所以你可以通过首地址加上偏移量直接计算出任意元素的地址这就是数组支持O(1)时间随机访问的根本原因。 我用一个生活化的比喻来解释数组就像电影院的一排座位座位号是固定的你买票时说“我要第5排第3座”检票员不用数过去也能直接告诉你位置在哪。链表就不是这样了链表更像一串藏宝线索你只知道下一张纸条在哪但不从头开始找就不知道第3张在哪。 这个差别直接决定了算法的设计方向 - 数组查询快下标访问是O(1) - 数组插入/删除慢因为要挪动后续所有元素平均是O(n) 所以在做数组相关题目时只要题目有“频繁查询”但“很少增删”的特征你就该优先想到用数组反过来如果数据频繁增删数组往往不是最优选择。 ### 1.2 为什么数组是算法面试的基础 代码随想录把数组放在训练营第一天是有讲究的。回顾我在面试中被问到的题目很多“花哨”题目本质上都是在数组上做文章 - **二分查找**针对有序数组的查询优化最典型的数组算法 - **双指针**在数组上进行原地操作的高效技巧 - **滑动窗口**数组子区间问题的标准解法 - **前缀和**数组区间查询的预处理方法 - **哈希映射**很多实现底层就是用数组加链表构造的 这些技巧有一个共同点它们都是在“连续内存”这个基础上做文章。比如双指针它的优势恰恰是因为数组支持随机访问你可以同时维护两个下标在数组上游走如果换成链表双指针就不能随意前后移动了。 学完Day01数组这一节你其实是在为后面所有数据结构和算法打地基。如果数组部分你能把二分查找的边界条件、双指针的移动逻辑都理解透后面学链表、字符串这些章节时会有一种“似曾相识”的感觉学起来轻松很多。 ## 2. 训练营Day01核心数组操作必须掌握的三个关键能力 ### 2.1 数组初始化的细节差异C/Python/Java对比 数组初始化的坑我相信大部分人都踩过。我最早学C的时候写出过这种代码 cpp int arr[10];然后就往里面填数据了压根没想过里面原本是什么。实际上这行代码分配了一块内存但里面是垃圾值如果你在上面做累加操作结果就是随机的。我Debug了一晚上最后发现是初始化的问题那次教训让我到现在都记得用数组前必须明确它的初始状态。C里常见的初始化方式我就不展开了重点说三种语言在“默认值”上的差别语言未显式初始化行为推荐做法C局部数组垃圾值int arr[100] {};或vectorint nums(n, 0)Python不存在未初始化[0] * nJava基本类型默认值如int为0new int[n]这个表格看起来简单但面试时问“数组初始值”是高频考点很多人就挂在“下意识认为所有语言都和Python一样”上。2.2 二分查找训练营第一个必须吃透的算法二分查找在Day01里会出镜率极高。代码随想录的数组章节会配一道经典题比如LeetCode 704。我见过太多人写二分的时候while循环条件写错、left和right边界更新错、死循环出不来。关键在于区间定义。我个人的习惯是坚持“左闭右闭”的写法也就是c int left 0, right nums.size() - 1; while (left right)这个写法的逻辑依据是因为left和right指向的元素都可能在下次比较中被检查所以left right时区间才有效。如果我用“左闭右开”那初始条件就要变成c int left 0, right nums.size(); while (left right)很多新手在这里栽跟头是因为他们不明确自己的区间是开还是闭然后一会儿用一会儿用代码看起来“差不多”但实际上边界条件完全不同。我给大家一个判断技巧你每次更新left和right时想想你写的是mid还是mid1并且反问自己“mid有没有可能还在下一轮搜索范围内”。比如左闭右闭写法如果nums[mid] target说明mid的位置不用再查了应该让right mid - 1如果nums[mid] target就让left mid 1。这样保证每次搜索区间都真正缩小了不会出现死循环。我上次用这个思路教一个学弟他之前一直写成right mid结果有时候能找到有时候找不到后来改成减一才恍然大悟原来边界条件从来不是死记硬背的。2.3 双指针法移除元素的原地操作思路Day01另一个主要内容是用双指针解决“移除元素”这类问题。LeetCode 27就是一个特别好的例子给你一个数组nums和一个值val你需要原地移除所有等于val的元素并返回移除后数组的新长度。暴力的实现是两层循环每找到一个val就把后面的元素整体前移时间复杂度O(n²)。但用双指针可以一次遍历搞定int removeElement(vectorint nums, int val) { int slow 0; for (int fast 0; fast nums.size(); fast) { if (nums[fast] ! val) { nums[slow] nums[fast]; } } return slow; }这段代码的核心思想是慢指针slow指向“下一个要填入的位置”快指针fast负责扫描整个数组。遍历过程中只要fast指向的元素不等于val就把它复制到slow的位置然后slow前进一步。由于fast永远比slow快所以不会出现在原数组中覆盖了还没扫描的元素。理解了这道题的快慢指针你其实就掌握了一大类“在原数组上原地操作”的题目。LeetCode 26删除有序数组中的重复项、LeetCode 283移动零本质都是同样的套路区别只在于判断条件移除元素判断nums[fast] ! val去重判断nums[fast] ! nums[slow - 1]移动零判断nums[fast] ! 0一个模板换三个判断逻辑就能解三题。代码随想录Day01把这个逻辑拆得很清楚我当时练完这几道题后有一种“任督二脉被打通”的感觉。3. 实操实录我用三种语言手写Day01经典题3.1 题目一LeetCode 704 二分查找我先用C写一版自己最习惯的左闭右闭class Solution { public: int search(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return -1; } };这里有个小细节很多人写mid (left right) / 2这在面试场景下没问题但严谨地说当left right很大比如接近INT_MAX时会溢出更稳的写法是left (right - left) / 2这个写法在工程上更常见。我再用Python写一遍因为面试时Python版往往更简练class Solution: def search(self, nums: List[int], target: int) - int: left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -1Python版里//是整除不会溢出所以直接写成(left right) // 2也可以。这里我想特别说一句算法训练营不只是“刷题”还要求你有能力用多种语言表达同一逻辑。面试官有时候会让你用两种语言对比写而数组初始化和整数除法这些细微差别很容易暴露基本功不扎实。3.2 题目二LeetCode 27 移除元素这道题我一开始用的暴力解法两层循环class Solution { public: int removeElement(vectorint nums, int val) { int size nums.size(); for (int i 0; i size; i) { if (nums[i] val) { for (int j i 1; j size; j) { nums[j - 1] nums[j]; } i--; size--; } } return size; } };这个解法能过但时间复杂度O(n²)在面试里不是一个好答案。你写出了暴力解之后面试官通常不会满意而是直接问“能不能优化到O(n)”。这时候双指针的写法就是标准答案。我当时做这道题的时候发现自己总是纠结在一个问题上“把后面的元素复制到前面会不会覆盖掉还没检查的元素”仔细推演了一遍之后才想明白因为快指针总是走在前面它已经检查过的元素才可能被覆盖而那些元素在慢指针位置上是不会再被读取了。所以覆盖是安全的。这个推演过程本质上就是理解双指针原地操作的底层逻辑。3.3 题目三LeetCode 977 有序数组的平方这道题在Day01的列表里我觉得设计得特别妙。它同时考了双指针和从后往前填充的思想。题目描述是这样的给你一个按非递减顺序排序的整数数组nums要求返回每个数字的平方组成的新数组要求也按非递减顺序排序。比如[-4, -1, 0, 3, 10]平方后是[16, 1, 0, 9, 100]排序后是[0, 1, 9, 16, 100]。最直观的思路是先平方再排序但这样时间复杂度是O(n log n)。能不能做到O(n)呢能。因为原数组有序负数部分平方后递减正数部分平方后递增所以最大数的平方一定在数组的两端不是最左就是最右。class Solution { public: vectorint sortedSquares(vectorint nums) { int n nums.size(); vectorint ans(n); int left 0, right n - 1; int idx n - 1; while (left right) { if (abs(nums[left]) abs(nums[right])) { ans[idx--] nums[left] * nums[left]; left; } else { ans[idx--] nums[right] * nums[right]; right--; } } return ans; } };这段代码的精髓在于从后往前填充。因为两端平方后可能很大你先确定最大的是谁放到结果数组的最后一位然后再比较剩下的两端。如果正序填充你还需要先找到“负转正”的分界点复杂得多。从后往前省掉找分界点的过程是一个非常典型的“逆向思维”技巧。4. 常见问题与排查技巧实录4.1 数组越界的几种隐蔽场景我在帮别人review代码时发现数组越界是刷题新手最常犯的错误而且很多越界不是一眼能看出来的。最常见的有三种第一种是二分查找中 mid 的计算导致 right 越界。比如右指针初始化为nums.size()时如果你用nums[mid]去访问mid不会等于right因为mid (left right) / 2在left right时永远小于right。但如果你用的是left right且right nums.size() - 1忘了减一的话一上来就nums[right]就越界了。第二种是双指针中慢指针和快指针的相对位置判断出错。比如移除元素的题目里如果快指针都走到末尾了你还继续让慢指针往后走那就会在慢指针位置上读到已经无效的数据。第三种是二维数组的越界这往往发生在“上下左右遍历”的题目中。比如你在遍历矩阵时判断相邻元素的方向忘了检查row - 1是否小于0就直接访问grid[row - 1][col]。我在写岛屿类题目时这种错误几乎每周都会犯一次。排查这类问题有一个特别实用的思路在for循环或while循环的入口处打印出当前的下标并和数组长度做对比。一旦发现某次访问的下标超出了[0, n-1]的范围立刻就能定位是哪个循环出了问题。4.2 逻辑正确但结果不对死循环的常见原因写二分查找和双指针时“死循环”是另一个高频问题。排查时你会发现很多时候不是语法错误而是区间更新时没有让搜索范围真正减小。举个例子左闭右闭的写法下如果nums[mid] ! target必须让left mid 1或者right mid - 1。如果你写成了left mid那么当left和right差1时mid可能永远等于left于是区间永远没有缩小死循环就出现了。我自己排查死循环时常用的方法是手动模拟三四轮不要直接跳到代码运行。比如你可以用nums [1, 3, 5, 7, 9]、target 7来推演每一步记录left、right、mid的值看变量是否按预期收敛。如果有一轮三个变量完全没变那基本就是死循环的根源。另外我强烈建议在代码里临时加一个计数器int cnt 0; while (left right) { if (cnt 100) { cout possible dead loop endl; break; } }这个“逃生门”看似很笨但在开发效率上极其实用尤其当你需要快速判断一个复杂的双指针循环是否正常结束时。4.3 调试数组题的高效工具与习惯数组题的调试其实是有套路的。我自己养成了一个习惯写完代码先不跑先在注释里把每一轮的数组变化画出来。比如移除元素这道题我会在草稿纸上写初始: nums [0,1,2,2,3,0,4,2], val 2 fast0, slow0: nums[0]0 ! 2, nums[slow] nums[fast] - [0,1,2,2,3,0,4,2] fast1, slow1: nums[1]1 ! 2, nums[slow] nums[fast] - [0,1,2,2,3,0,4,2] fast2, slow2: nums[2]2, skip ...这个习惯刚开始看起来慢但坚持下来后你会发现自己对“谁在移动、谁在写入”的感受特别直观写复杂一点的滑动窗口也不容易头晕。代码调试工具的话如果你用的IDE我推荐在循环中打条件断点比如当fast 3的时候才停下来观察如果用的是纯文本编辑器可以用print临时输出关键变量。调试数组题的关键是一定要能看到遍历过程中数组的内容变化而不是只盯着一两个变量看。5. 从Day01出发数组学习的进阶路线5.1 Day01之后这些数组题建议按顺序做代码随想录数组part01的内容是整个数组章节的第一块拼图。如果你已经做完二分查找、移除元素、有序数组平方这三道题接下来我建议你去刷这几道经典题它们之间是循序渐进的LeetCode 209. 长度最小的子数组滑动窗口思想第一次接触“窗口内维护一个和”的概念LeetCode 59. 螺旋矩阵II模拟法不涉及复杂算法但极其考验对边界和方向的控制LeetCode 56. 合并区间排序加区间合并是面试高频题LeetCode 189. 旋转数组经典的三次反转很多大厂面试官喜欢考这几道题的共同点是都在“数组”这一个数据结构上做文章但考察的技巧各不相同。如果你Day01的基础打得牢做这些题时会发现很多思路都是相通的。比如滑动窗口的窗口收缩逻辑就和双指针的边界更新逻辑很相似。5.2 数组题最常见的面试追问方式面试官很少只问“这道题怎么做”他们更常见的追问方式包括追问1时间复杂度是多少能不能优化当你给出O(n²)的解时面试官大概率会直接要求优化到O(n)。这时候你如果掌握双指针就能接得住。比如“移除元素”的暴力解法被问“还能更快吗”你立刻想到快慢指针这个转折点就是一个典型的加分项。追问2如果数组特别大内存装不下怎么办这道题就涉及外部排序或者分块处理了已经不是单纯的“数组”问题。但在训练营阶段接触这个问题可以让你意识到数组操作的边界不只是代码层面还有存储层面的考量。追问3如果数组有重复元素你的代码还能跑对吗这尤其爱问在二分查找上。比如LeetCode 34在排序数组中查找元素的第一个和最后一个位置它要求你在有重复元素时分别找到左右边界如果你只会写基本的二分查找很容易卡住。从Day01的“标准二分”到这种“边界二分”是算法水平的真实分水岭。5.3 学习节奏与训练方法建议我结合自己当年刷代码随想录的经验给刚开始的人几个建议。第一个建议不要只刷一遍就过。数组part01的题目看着简单但每一道题都值得你用“一题多解”来训练。二分查找的题目你试试左闭右闭写一遍再试试左闭右开写一遍体会一下差别。移除元素那题你试试双指针写一遍再看能不能用暴力解对照。这样做一遍的收获抵得上别人刷三遍。第二个建议在纸上画出每一步的数组变化。算法训练营的作用不只是让你会写代码更重要的是让你“看懂”代码。纸上画图是花时间最少但见效最快的方式尤其当你觉得双指针很容易绕晕的时候。第三个建议允许自己卡住。我看到很多人做不出题就焦虑其实完全没必要。一道算法题卡半小时甚至一小时是再正常不过的事。我当时刷螺旋矩阵那道题花了一个下午才理清方向控制的逻辑但理清之后后面所有模拟类的题我都不怕了。卡住不是坏事卡住后想一想“我为什么卡住”比快速看答案的效果好得多。6. 写在最后数组并不简单但它是你最好的起点数组作为算法训练营的第一课很多人会觉得“我早就学过数组了这部分可以跳过”。但我在实际面试和带新人的过程中发现恰恰是数组这种“看起来很基础”的内容最能检验一个人对数据结构的理解深度。我遇到过面试者能流畅说出哈希表怎么扩容却写不好一个边界正确的二分查找也遇到过简历上写着“熟悉数据结构与算法”但在“有序数组平方”这道题上用了O(n log n)解法却意识不到可以优化到O(n)。这些差距往往不在于你学了多少花哨的算法而在于你有没有把最基础的东西彻底吃透。Day01的数组part01代码随想录安排的内容其实很少只有几道题、几个核心技巧。但你要是真的按照我上面说的方式去练——手写三遍、画出每一步的数组变化、尝试不同语言实现——你会发现自己后续学链表、哈希表、字符串时底气和别人完全不一样。最后分享一个小感受学算法的第一周是最容易放弃的因为你可能觉得自己刷题又慢又笨。请不要急着否定自己。我当时Day01的双指针也绕了挺久但熬过这个坎之后后面越学越顺。数组是你和算法之间建立信任的第一步把它走稳后面的路会开阔很多。