训练营 Day01 的标题是“数组 part01”不少同学点进来之前觉得这题也太简单了数组谁不会啊int a[10]从头到尾遍历不就行了可实际带训的时候第一天打回来的作业一大半是栽在两个地方704 二分查找写着写着开始死循环27 移除元素写完倒是能跑一看空间复杂度笑出声或者干脆遍历时把下标搞越界。数组这一节是整个刷题链条里最容易被低估的一课因为它表面上考的是“你会不会写循环”实际考的是你懂不懂“区间到底该怎么定义”。这篇内容我按训练营的 Day01 路线完整梳理一遍先讲数组在内存里的真相再逐行拆解二分查找的两种区间写法最后把移除元素的暴力解和快慢指针解都写出来对比。面向的是刚开始刷题的人也适合那些刷了几十题但边界条件老是靠背、过后就忘的同学。把这些“为什么”弄明白比闷头刷十道重复题目都值。1. 数组的底层逻辑第一天为什么要从内存讲起1.1 数组是一排连续的“标准间”数组的定义可以浓缩成一句话相同类型的元素连续存放在一段连续的内存地址里。这句话每个字都有代价。“相同类型”意味着每个元素占的内存大小完全一致编译器才能用“首地址 下标 × 元素大小”这个公式直接算出任意元素的地址。这也是数组下标从 0 开始而不是从 1 开始的原因——下标 0 的元素地址就是首地址不需要再做一次减法。在底层硬件上少一次计算就是实打实的性能节省。打个比方数组就像一栋每层户型完全相同的公寓房间号从 0 开始编排。你要找第 k 间房不需要从 0 号房一路走过去直接根据“楼栋入口在哪儿 第 k 间的偏移量”算出来就行。这种随机访问能力是 O(1) 的是数组最大的本钱。但它也有代价你想在中间某个位置插进一个住户后面所有房间的人都得搬一次家所以数组的插入和删除是 O(n) 的。很多新手把“数组查找快”和“数组操作快”划等号这是第一天就要纠正的概念。1.2 三种语言里数组的脾气完全不一样同样是数组不同语言底层的“性格”差别很大直接用 C 模板做题的人切到 Python 会很不适应原因就在这。C/C 里数组是真正分配在栈或堆上的连续内存int a[5] 就是 20 个字节的连续空间你可以拿指针自增去移动也可以直接对下标取地址。数组大小固定越界访问编译器不拦运行时会读出一堆随机数据这是无数神秘乱码和崩溃的源头。Java 的数组是一个对象int[] arr new int[5] 会在堆上开辟一块连续内存arr 变量只保存引用。好处是有 length 属性、有越界检查坏处是“数组变量”和“数组本体”是分开的传参传的是引用函数里改数组外面跟着变——这个特性刷题时经常被用来“偷懒”但也会让不熟悉引用语义的人困惑。Python 的 list 更特殊它底层其实是个“指针数组”每个槽位存的并不是元素本身而是指向真实对象的引用。所以 Python list 能装任意混合类型代价是每个元素多一次指针间接访问存储小整数等场景下比 C 数组更耗内存。Python list 自带 append、pop 这些动态扩容能力看着方便但刷算法题时要清醒list.remove(val) 本身是 O(n) 的线性查找加搬移在循环里反复 remove 很容易写出 O(n²) 而不自知。第一天就把这些差异想清楚后面做“原地修改、返回新长度”这类题时会少走很多弯路。思路是一样的只是语言表达差异大不能指望把 C 解法照搬到 Python 上一点不改。1.3 数组没有真正的删除数组还有一个反直觉的事实它没有真正的“删除”。删除的本质是“把后面的元素往前覆盖”数组本身长度不变只是逻辑上的有效部分变短了。比如 [3, 2, 2, 3]你想删掉所有 3一次覆盖之后数组还是 4 个长度只不过下标 0、1、2 位置变成了 [2, 2, 3]下标 3 的位置还残留一个没人管的 3。算法题里处理这种情况通常要求你“返回新的有效长度”而不是真的把数组缩成三格。理解这一点对 27 题至关重要也能解释为什么很多同学“用库函数也能过面试官却摇头”——因为题目考的就是你会不会在原地用覆盖思想完成 O(1) 额外空间的操作而调用语言自带的删除接口既不是这个空间复杂度也没有体现算法思路。2. 704 二分查找把“区间不变性”刻进脑子2.1 二分查找到底在干什么二分查找704 题是几乎所有题目集里的“入门主题曲”原因不是它难而是它能用最小规模考察你对循环不变量的掌握程度。题目本身很简单在升序整数数组里找一个目标值存在返回下标不存在返回 -1。暴力做是 O(n)二分做是 O(log n)数据规模到 10 亿时差距是 30 次和 10 亿次。二分的核心前提有两个数组有序且基础版里不要求处理重复元素。为什么必须有序因为每一步都在利用“中间值的大小能判断目标在左半边还是右半边”这个单调性。没有这个前提你砍掉一半搜索空间的依据不成立二分就退化成盲猜。每次取 mid (left right) / 2比较 nums[mid] 和 target相等直接返回target 更大说明目标在右半边左边界收紧到 mid 1target 更小说明在左半边右边界收紧。这个“边界怎么收”的具体写法完全取决于你对区间的定义。这是二分查找唯一的核心分歧点也是所有 bug 的源头。2.2 左闭右闭 [left, right] 的写法与边界标准写法一区间定义为 [left, right]也就是 left 和 right 都是“取得到”的。代码长这样// 区间定义为 [left, right]左右边界都取得到 int search(vectorint nums, int target) { int left 0; int right nums.size() - 1; // 关键1right 是最后一个有效下标 while (left right) { // 关键2left right 时区间还有一个元素要查 int mid left (right - left) / 2; // 防溢出写法 if (nums[mid] target) return mid; if (nums[mid] target) left mid 1; else right mid - 1; // 关键3mid 已经查过直接排除 } return -1; }这里三个“关键”是一套完全联动的逻辑。因为 right 取得到所以初始 right size - 1因为 [left, right] 在 left right 时仍然包含一个元素比如区间 [5, 5] 里的 5 是有效下标所以循环条件必须是 left right因为 mid 已经检查过且不匹配新的搜索区间必须把它排除所以 right mid - 1 而不是 right mid。如果写成 right mid配合 left right 的条件会出现死循环——区间一直包含已经排除的 mid左右边界反复横跳。为了方便记忆可以把这三条绑定在一起取得到 → 循环等号可入 → 右边界敢减一。Python 版本只是语法差异def search(nums: list[int], target: int) - int: left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -12.3 左闭右开 [left, right) 只需改两处第二种写法区间定义为 [left, right)左闭右开right 这个下标本身取不到。它的代码长这样// 区间定义为 [left, right)right 取不到 int search(vectorint nums, int target) { int left 0; int right nums.size(); // 关键1right 取不到所以从 size 开始 while (left right) { // 关键2left right 表示空区间不进入循环 int mid left (right - left) / 2; if (nums[mid] target) return mid; if (nums[mid] target) left mid 1; else right mid; // 关键3mid 已被排除[left, mid) 不包含 mid } return -1; }这一套的绑定规则是取不到 → 空区间跳出循环 → 右边界直接等于 mid。两套写法看着只差“right 初始化减不减一”“while 里有没有等号”“right mid 还是 mid - 1”三处实际上是两套完全自洽的逻辑。新手最常见的死法就是把它们混着写初始化按 [left, right]循环条件却写成 left right或者右边界写成 right mid。单看每一处似乎都“有点道理”合在一起就必然导致漏查或死循环。我的建议是刚开始只背熟一套。我个人习惯左闭右闭 [left, right]因为它的语义更符合直觉区间左右都包含和“查找范围”的日常认知一致。等这一套熟练到能解释每一个等号和减一再回头对照左闭右开一天补一个就够。2.4 二分最容易翻车的三个现场二分查找翻车现场我几乎每一期都能见到同样几个列出来供大家自查第一死循环。特征是不报错程序卡住不动。常见原因一个是区间混用一个是把 left 更新成了 mid。为什么不能写 left mid因为在某些区间状态下 mid 会等于 left边界不动循环永远出不去。记住基础二分里搜索区间每一次都必须严格缩小左边界至少加 1右边界至少减 1或者取 mid 但不含 mid。第二越界访问。比如 nums[mid] 里的 mid 算出负数或超出 size通常也是区间混用导致。还有一种隐蔽情况数组只有一个元素时如果循环条件写错初始 mid 不参与判断就直接返回 -1查不到本来存在的答案。第三溢出。int mid (left right) / 2当 left 和 right 都接近 int 上限时left right 会溢出成负数mid 变负直接越界。普通测试数据一般触发不了但面试官特别喜欢追问这个。标准安全写法是 mid left (right - left) / 2数学上等价但不会溢出位运算写法 mid left ((right - left) 1) 也常见效果一样。很多同学背模板只关心“怎么让样例通过”但训练营第一天真正要练的是“能不能用一句话解释为什么这样写就不会错”。二分查到最后拼的不是代码量而是对区间不变量的理解。解释不出来换一道差不多的题比如搜索插入位置照样卡壳。3. 27 移除元素快慢指针的第一次实战3.1 题目问的是“长度”不是“删除”27 题移除元素要求是给你一个数组 nums 和一个值 val原地移除所有数值等于 val 的元素并返回移除后数组的新长度。不需要考虑数组中超出新长度后面的元素。这句话有三层含义要读明白。第一“原地”意味着你不能新建一个数组把不等于 val 的元素过滤出来再赋回去——那样额外空间是 O(n)和题目考察的 O(1) 空间原地操作相去甚远。第二返回的是新长度不是新数组所以数组末尾残留旧值也无所谓只要有效前缀正确。第三基础版不要求保持元素相对顺序这给了实现更大自由度。做题之前先在纸上走一遍过程感觉会完全不一样。比如 nums [0, 1, 2, 2, 3, 0, 4, 2]val 2。你手动把每个 2 划掉剩下的依次往前挪最后有效部分就是 [0, 1, 3, 0, 4]长度 5。这个过程其实就是快慢指针在干的事。3.2 暴力双重循环慢在哪先看暴力解。思路很直接从头遍历发现 nums[i] val就让 i 之后的所有元素整体前移一位同时有效长度减一。因为 i 位置被后面元素覆盖了还要 i-- 回头重新检查这个新搬来的元素。代码长这样int removeElement(vectorint nums, int val) { int n nums.size(); for (int i 0; i n; i) { if (nums[i] val) { for (int j i 1; j n; j) { nums[j - 1] nums[j]; } i--; // 回头检查覆盖过来的元素 n--; // 有效长度减一 } } return n; }这个解法正确性没问题但每次遇到 val 都要搬移后面所有元素最坏情况数组全是 val下是 O(n²)。更关键的是i-- 这个细节特别容易写丢。丢了会怎样i 直接跳过覆盖过来的新元素连续重复值时就会漏删。很多同学样例能过、提交就挂基本都挂在这个 i-- 上。暴力解的意义在于帮你理解“覆盖”这个动作本身它不是把 val 从内存里抹掉而是把后面的元素逻辑前移、有效长度收缩。理解了这一点再看快慢指针就顺理成章。3.3 快慢指针为什么能做到 O(n)快慢指针的核心思想一句话概括让一个快指针负责“发现值得保留的元素”让一个慢指针负责“记录下一个该覆盖的位置”。两个指针都从 0 出发快指针每次前进一格慢指针只在发生覆盖时前进。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]; slow; } } return slow; // slow 就是新长度 }为什么这个写法是对的可以把它理解成“慢指针左边永远是已经筛选好的、全部不等于 val 的前缀”。快指针遍历整个数组每遇到一个不等于 val 的元素就复制到慢指针的位置并让慢指针前进遇到等于 val 的元素就跳过不产生任何复制。最终慢指针停在最后一个保留元素的下一个位置它的数值恰好等于保留元素的个数也就是新长度。这个过程每个元素最多被复制一次所以时间复杂度 O(n)额外空间只有两个下标O(1)。相比暴力解它把“遇到 val 就搬移后面所有元素”这个高成本操作换成“遇到非 val 就拷贝一次到前面”从推式变成拉式这是双指针手法非常典型的思维转变。Python 版本def remove_element(nums: list[int], val: int) - int: slow 0 for fast in range(len(nums)): if nums[fast] ! val: nums[slow] nums[fast] slow 1 return slow注意 Python 里 list 的 len 是动态的但这里的循环用 range(len(nums)) 在开始时固定了快指针的遍历范围。因为我们是原地覆盖、不实际删除元素nums 的长度始终不变所以这样遍历是安全的。如果哪天真调用了 pop 或 remove循环范围就会出问题。这也是我强调用指针写法而不是依赖语言自带删除接口的原因。3.4 这一套模板能直接迁移的题型快慢指针这套模板价值极高第一天学会它后面至少三道题可以无缝套用。一是有序数组去重。给定有序数组原地删除重复元素使每个元素只出现一次返回新长度。思路就是把“跳过等于 val”改成“跳过和前一个保留元素相同的值”慢指针维护的仍然是“不重复前缀”。二是移动零。把数组里所有 0 移到末尾同时保持非零元素相对顺序。这题可以把 0 当成要“移除”的 val第一遍快慢指针把所有非零往前排剩下的位置补 0边界用新维护的长度截断即可。三是有序数组的平方。先找到正负分界点再用双指针从两端向中间归并平方结果。这个虽然和快慢指针略有不同但核心还是“两个指针互相配合维护结果数组”。能看出规律吗快慢指针适合所有“原地筛选 返回有效长度/前缀”的题目。遇到这类题先问自己三个问题快指针负责什么慢指针维护什么语义什么条件下慢指针前进三个问题想清楚代码基本就出来了。4. 第一天的坑位速查表与复盘方法4.1 报错症状对照速查表把第一天最常见的报错和原因整理成一张表排查时对号入座症状常见原因修复方向二分查找死循环循环条件与区间定义不匹配left 更新成 mid统一用一套区间写法左边界至少加 1二分查找漏掉最后一个元素左闭右闭却用了 left right左闭右闭必须用 left rightmid 计算出负数或越界(left right) 溢出改成 left (right - left) / 2移除元素漏删暴力解忘记 i--覆盖后必须回头检查或改用双指针移除元素结果多算/少算返回了原长度而不是 slow新有效长度就是 slow 值样例通过但大数据超时写成了 O(n²) 暴力换成快慢指针 O(n) 解法这张表建议保存下来第二天做新题之前先扫一遍。很多人的二分 bug 不是不会写而是几种写法在脑子里打架最后缝合成一个四不像。每次提交前先明确告诉自己“我现在用的是哪一套区间定义”比反复试错高效得多。4.2 第一天怎么安排练习节奏训练营第一天的量其实不大核心就两题加理论基础但节奏感很重要。我的建议是这样安排先花 30 到 40 分钟把数组理论基础和两种二分写法看清楚不要急着做题。重点不是记住代码而是能解释“为什么 right mid - 1”“为什么 while 里要等号”这类问题。然后花 20 分钟手写一遍左闭右闭版本注意是手写别开着模板直接抄肌肉记忆和眼睛记忆完全不是一回事。写完二分再花 30 分钟做移除元素。先自己写暴力解法把坑踩一遍比如忘写 i--再切换到双指针。我不反对先暴力后优化因为暴力的失败过程能让你真正理解为什么要优化。最后留 15 分钟把两题的复杂度分析写一遍时间、空间、为什么这样是最优的。第二天一定要回头重做这两题而不是急着学新题。间隔一天之后的默写才是真正属于你自己的模板。4.3 实操里的几个加分细节最后分享三个我在实际练习中发现很有用的小习惯。第一个二分模板用注释固定区间定义。我自己的写法会在 right 初始化的那一行写注释// 区间 [left, right] 左闭右闭。每次检查代码时所有边界条件都对齐这套定义不容易漂移。等你会写第二种区间后也可以在注释里标清楚两个模板并用时不容易拿混。第二个移除元素这类题的输出检查方法。本地调试时把结果数组的前 newLength 个元素打印出来确认它们全不等于 val再看数组末尾残留下的旧值不用管。如果你直接打印整个数组看到末尾有残留 val 会以为是 bug其实那是正常现象。第三个关于“一题多解”的投入节奏。第一遍不要追求把所有解法都看完先把一种解法完全吃透、能默写、能讲清楚再看第二种。贪多嚼不烂区间边界这种东西两个版本同时学特别容易混。等左闭右闭已经成了条件反射再去补左闭右开一天补一个就够。数组 part01 的真正收获不在你做对了那两道题而在你开始认真对待“边界”。边界问题在后面的链表、二叉树、滑动窗口里会以各种变形反复出现第一天建立起来的区间意识和指针分工意识到最后会发现是所有复杂算法题的地基。这也是训练营把数组放在第一天的原因——先爬坡后面才走得稳。
