算法训练营DAY1：数组特性、二分查找与双指针全解析

算法训练营迈进DAY1，今天的题单是数组四连击：数组的特性、二分查找、移除元素、有序数组的平方。光看名字全是最基础的入门内容，但真正自己动手写一遍才发现，每一道题都不是在考“你会不会写循环”，而是在逼你回答同一个问题：你到底理不理解数组在内存里是怎么存在的。

为什么要从数组开始？因为数组是绝大多数进阶数据结构的物理基础。栈、队列、哈希表、堆，底层几乎都离不开一段连续内存。更重要的是，数组题的套路高度可复用：二分查找的边界处理、双指针的区间维护、原地操作的覆盖删除，这三个技能在后面的链表、字符串、滑动窗口里会反复出现。这篇文章把DAY1的四个主题完整拆开，每道题都给出完整代码、手推过程和踩坑记录。刚准备刷算法题的人可以照着学，已经刷过一遍的人也可以用来查漏补缺。

1. 数组特性：所有坑都藏在“连续”两个字里

1.1 三个底层事实决定一切

数组最核心的事实只有三个：元素类型相同、内存空间连续、大小固定。这三个事实像三条物理定律，直接决定了数组在算法题里的一切行为。

第一个是随机访问。因为内存连续，给定起始地址之后，直接通过“起始地址 + 下标 × 单个元素大小”算出目标位置，所以访问任意下标都是O(1)。这是二分查找能成立的前提：如果访问第i个元素要O(n)，那每次取mid的成本都不可接受，整个算法直接不成立。正是因为这种O(1)访问，算法题里讨论数组时，几乎从不说“访问”，只说“移动”。

第二个是插入删除要移动。在任意位置插入或删除元素，为了维持“连续”，必须把后面的元素整体搬动，平均O(n)。这是移除元素这道题以及所有“原地操作”题目的物理根源。为什么算法题里一遇上数组就爱考“移动”？因为访问没有难度，移动才有。

第三个是大小固定。C++里静态数组大小在编译期就得确定，动态数组（vector）虽然支持扩容，但扩容本质上是“申请新空间 + 整体拷贝”，代价不是免费。这导致很多题目刻意要求“原地操作，不能新建数组”，本质就是在约束你的空间复杂度。

可以用一个生活场景帮助记忆：数组就是电影院一排固定数量的座位。你要在第3个座位插一个观众，从第3个座位起的每个人都要往旁边挪一格；你说“第3个座位的观众走了”，也不会真的把座位拆掉，而是后面的人依次补上来，把空位填掉。这个“补位”的过程，就是移除元素里快慢指针正在做的事。

1.2 不同语言里的“连续”并不完全相同

这一点初学者很容易忽略。C++的二维数组是一段真正连续的内存，int a[3][4]本质上是12个int在内存里依次排开；Java的二维数组是“数组的数组”，每一行是独立的一维数组对象，行与行之间并不保证物理连续；Python的list则更特殊，它存的是对象引用，不是元素本体，所以list里混着整数、字符串、None都没问题，内存层面只是“引用连续排列”。

这个差异在刷题时的影响：C++里可以做指针算术，Java和Python里基本不行；但算法题考察的是逻辑复杂度，不是物理内存布局，所以大多数题目并不依赖这些语言特性。真正该记住的是：无论哪个语言，erase、remove、pop这类操作底层都是移动元素，只是把O(n)的活儿藏进了标准库而已。理解这一层，是后面“移除元素为什么别直接调库函数”的基础。

我个人刷题的经验是：不用纠结语言层面的细微差别，但脑子里一定要有“元素搬家”的画面。你一旦能看到那个画面，双指针的写入、覆盖的顺序、传参的边界就都不会犯糊涂。数组是算法的地基，不是因为它简单，而是因为它逼你先想清楚内存和复杂度，后面链表、树、图全都是在这两个概念之上盖楼。

2. 二分查找：你不是在写循环，是在维护一个区间

2.1 左闭右闭和左闭右开，两种写法都必须会

二分查找（Binary Search）的适用条件有两个：数组有序，且没有重复元素。无重复是为了方便精确定位目标值；如果数组里有重复，想找左边界或右边界还得再加逻辑，那是后面的进阶题。核心思路一句话：每次把搜索区间砍半，复杂度O(log n)。

几乎所有初学者的bug都出在同一个地方：区间定义和循环条件对不上。下面两种写法都行，但必须全程只认一种。

左闭右闭，区间[left, right]，意思是left和right都是“有效的、可访问的”下标：

• while (left <= right)：因为left == right时区间里还剩最后一个元素，必须再查一次
• 当nums[mid] > target时，mid已经查过并且大了，区间缩小到[left, mid - 1]
• 当nums[mid] < target时，区间缩小到[mid + 1, right]
• 循环退出还没返回，说明目标不存在

左闭右开，区间[left, right)，right是取不到的下标：

• while (left < right)：因为left == right时区间长度已经是0
• 当nums[mid] > target时，right = mid，区间变成[left, mid)，mid本身被排除
• 当nums[mid] < target时，left = mid + 1

很多人卡在“为什么左闭右开里是right = mid，而不是right = mid - 1”。我的理解方法：左闭右开本来就约定right不进入区间，你把right设成mid，效果就是“mid及以后全部排除”。同时，mid已经被比较过且大于target，排除它完全正确。反过来，如果是左闭右闭，right指向的元素本身也会被检查，mid已经确定不是答案，就必须写成mid - 1，否则下次循环会把mid重新纳入搜索，造成死循环。

为了直观，直接看对比表：

2.2 完整代码与手推过程（704题）

先给C++版本：

class Solution { public: int search(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] < target) { left = mid + 1; } else { return mid; } } return -1; } };

Python版本：

class Solution: def search(self, nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] > target: right = mid - 1 elif nums[mid] < target: left = mid + 1 else: return mid return -1

拿一个命中过程推演一遍。nums = [1, 3, 5, 7, 9, 11, 13]，target = 7：

• left = 0, right = 6, mid = 3
• nums[3] = 7，正好命中，返回3，一次就找到了。

再走一个不命中的过程，target = 8，关键看区间怎么收拢：

• left = 0, right = 6, mid = 3，nums[3] = 7 < 8，所以left = 4
• left = 4, right = 6, mid = 5，nums[5] = 11 > 8，所以right = 4
• left = 4, right = 4, mid = 4，nums[4] = 9 > 8，所以right = 3
• 此时left = 4 > right = 3，循环退出，返回-1

注意第3步那一轮：left == right，区间里只剩下下标4这一个元素，如果不是left <= right，这步根本不会执行，那么nums[4]永远不会被检查。这个细节，就是边界误判的根源。

2.3 mid为什么要写成left + (right - left) / 2

数学上(left + right) / 2和left + (right - left) / 2完全等价，但工程上不一样。如果left和right都接近int类型的上限（比如2^31 - 1），left + right这一步会先溢出成负数，mid直接算错。用left + (right - left) / 2，先做差再除2，中间结果始终在安全范围。虽然日常刷题很少遇到那么极端的数组长度，但这个习惯最好从第一次写二分就养成，后面很多题目都会复用这个写法。

2.4 排查边界bug的“最小用例法”

说到二分查找的调试，我最常用的排查方式是：写完后立刻用长度为1和长度为2的数组各测一遍，尤其是把target取在数组右端点上。

比如nums = [1, 3]，target = 3，如果你写的是左闭右闭却用了while (left < right)：

• left = 0, right = 1, mid = 0
• nums[0] = 1 < 3，left = 1
• 循环条件left < right不成立，退出，返回-1

明明数组里就有3，却返回找不到。原因就是整型除法向下取整，mid永远偏左，加上while条件没覆盖最右端，右端点就这样被漏掉了。这个例子我每次讲二分都要拿出来，因为它是“区间定义和循环条件不匹配”最经典的现场。

3. 移除元素：快慢指针不是在“删”，是在“保留”

3.1 暴力解法为什么慢

题目是经典的第27题：给你数组nums和一个值val，要求原地移除所有等于val的元素，返回新长度，空间复杂度O(1)，不额外开数组。

最容易想到的写法是两层循环：外层i扫描整个数组，遇到nums[i] == val时，内层把i + 1到末尾的所有元素整体前移一位，同时记录长度减1。这个思路在元素比较少的时候没问题，但最坏情况下数组全是val，每检查一个元素就要把剩余元素全部移动一次，总操作量接近n²/2，是O(n²)。n到一万这种规模，肉眼可见地卡。

那能不能用erase？库函数一行确实快，但想清楚：erase内部就是“把目标位置后面的元素依次前移”，本质还是O(n)，只是把过程封装了。刷题的价值不在于调库，而在于亲手实现这个移动逻辑，这样你才不会在面试官追问“你讲讲erase底层做了什么”的时候哑口无言。

3.2 快慢双指针的完整推导

双指针写法代码很短，但背后的思维路径值得完整走一遍。

设置两个下标：slow是慢指针，表示“下一个可写入的位置”；fast是快指针，负责扫描数组里的每个元素。fast每到一个位置，判断它是不是val——如果不是，就把这个元素赋给nums[slow]，然后slow加1；如果是val，什么都不写，fast继续走。最终，slow前面的部分全部是非val元素，返回slow就是新长度。

C++实现：

class Solution { public: int removeElement(vector<int>& 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; } };

Python实现：

class Solution: def removeElement(self, 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

拿nums = [3, 2, 2, 3]，val = 3走一遍：

• slow = 0, fast = 0，nums[0] = 3等于val，跳过
• fast = 1，nums[1] = 2不等于val，nums[0] = 2，slow变为1
• fast = 2，nums[2] = 2不等于val，nums[1] = 2，slow变为2
• fast = 3，nums[3] = 3等于val，跳过
• 返回slow = 2

最终的数组前两位变成[2, 2]，后面的位置残留什么不重要，因为返回的长度只保证前两位有效。

这里最关键的思维转换是：移除元素不是“删除等于val的位置”，而是“把所有不等于val的元素按顺序搬到前面”。脑子里一旦把关注点从“删什么”切换成“留什么”，代码就是顺水推舟。这个模型在面试里极其常见，因为很多“原地过滤”类题目都是同一个思想。

3.3 一个模板通吃三道变体题

DAY1里只有移除元素这一题，但它的模板可以直接迁移到至少两道经典题上。

第26题，有序数组去重：nums已经有序，原地删除重复项，返回新长度。模板几乎不变，唯一的区别是把“不等于val”换成“不等于上一个保留的值”。

第283题，移动零：把数组里的0全部移到末尾，同时保持非零元素相对顺序。可以先调用快慢指针把所有非零元素搬到前面，再把数组后半段全部置0；也可以用交换的方式在扫描过程中直接完成。

把这三道题放在一起对比，规律特别清晰：都是快慢双指针，都是“slow维护有效前缀，fast负责探索”，区别只在写入条件。所以DAY1如果确实吃透了移除元素，后面这三道变体基本都是送分题。

3.4 实际写题时踩过的坑

这个题我第一次提交时栽了两个跟头。第一个是忘记返回值，函数要求返回新长度，我改完数组忘了return，编译通过但是测试全红。第二个是心里没底：当fast已经超过slow时，nums[slow] = nums[fast]覆盖的是早就不需要的位置，不会破坏后面还要读的fast指向的元素，所以这个顺序是安全的。但如果没有想通这一点，写的时候总有一种担心覆盖掉有效数据的紧张感，容易手抖改成从后往前写，反而把逻辑搞乱。

还有个小边界：如果val根本不在数组里，那fast每走一步几乎都要写入nums[slow]，最后slow等于原数组长度，返回原长度，完全正确。如果数组为空，循环不执行，slow = 0，也正确。这两种情况很值得手动测一测，它们能帮你确认代码没有隐藏的越界问题。

4. 有序数组的平方：最大值只在两端，所以双指针要对向收缩

4.1 先平方再排序不是最优解

第977题的描述很直接：给你一个按非递减顺序排序的整数数组，返回每个数字的平方组成的新数组，同样按非递减排序。

最直接的做法是两件事：把每个元素原地平方，然后排序。这个解法能通过测试，时间复杂度是O(n log n)，问题在于——题目送你的“原数组有序”这个条件，一点都没用上。凡是告诉你原序列有序的题，先别急着sort，大概率存在利用了有序性的更优解。这算是刷题久了形成的一种条件反射。

4.2 “绝对值从两端向中间递减”的观察

为什么原数组有序能带来优化？关键在于符号。负数的平方等于它绝对值的平方。原数组有序，意味着元素的绝对值从两端往中间递减：最左边可能是一个绝对值很大的负数，最右边是一个绝对值很大的正数，而靠近0附近的元素绝对值最小。换句话说，平方后最大的数，只可能出现在最左端或最右端，绝不会出现在中间。

基于这个观察，用两个指针一左一右，每次比较两端平方谁更大，把大的那个放进结果数组的末尾，然后移动对应的指针。结果数组从后往前填，每次都能确定一个“当前剩下的最大值”，最后得到的就是一个从小到大排好序的结果。

C++实现：

class Solution { public: vector<int> sortedSquares(vector<int>& nums) { int n = nums.size(); vector<int> res(n); int i = 0, j = n - 1, k = n - 1; while (i <= j) { int a = nums[i] * nums[i]; int b = nums[j] * nums[j]; if (a > b) { res[k--] = a; i++; } else { res[k--] = b; j--; } } return res; } };

Python实现：

class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: n = len(nums) res = [0] * n i, j, k = 0, n - 1, n - 1 while i <= j: a, b = nums[i] * nums[i], nums[j] * nums[j] if a > b: res[k] = a i += 1 else: res[k] = b j -= 1 k -= 1 return res

拿[-4, -1, 0, 3, 10]手推一遍：

• i = 0对应(-4)²=16，j = 4对应10²=100，100更大，res[4]=100，j变3，k变3
• i = 0对应16，j = 3对应3²=9，16更大，res[3]=16，i变1，k变2
• i = 1对应(-1)²=1，j = 3对应9，9更大，res[2]=9，j变2，k变1
• i = 1对应1，j = 2对应0，1更大，res[1]=1，i变2，k变0
• i = 2对应0，j = 2对应0，相等时走进else分支，res[0]=0，j变1
• i = 2 > j = 1，结束，结果是[0, 1, 9, 16, 100]，完全正确

4.3 为什么从末尾填，而不是从开头填

我刚开始想当然要从结果数组开头填最小的数，但随即发现一个问题：最小的平方数对应的是“绝对值最小的元素”，而这个元素在有序数组里的位置是中间某个不确定的地方。你得先找到它，再往两边扩展，定位成本很高。反而是“最大的数一定在两端”这个性质是免费的，不用找，就在那里。既然最大最好确定，那就从末尾往前填，每次都能确定一个值。这是个很实用的策略：构造答案时，哪头更容易确定，就从哪头开始填。

4.4 DAY1里的两种双指针模型

把移除元素和平方数组放在一起，会发现DAY1实际上教了两个双指针模型。

移除元素用的是同向双指针：快慢两个指针都从头向尾走，慢的负责写，快的负责读，维护一个前缀有效区。平方数组用的是对向双指针：一个在头一个在尾，往中间收缩，每次确定一个当前最大或最小，填入结果数组。这两种模型在后面的经典题里会反复出现，比如有序数组的两数之和II，就是一个指针头一个指针尾，根据和的大小决定移动哪边；再比如盛最多水的容器，同样是两端收缩。

所以DAY1的划算之处就在这里：四道题，一个二分模板，两个双指针模型，全是后续刷题的主干技能。第一天的题量不大，但每一道都值得反复写，道理就在这。

5. DAY1复盘：看懂是别人的，写出来才是自己的

5.1 两条主线：区间不变量和指针语义

把四道题合起来看，能提炼出两条清晰的思维主线。

二分查找训练的是“区间维护”。你写的不是一个简单的while循环，而是一个不变量：无论区间怎么缩，target只要存在于数组中，就一定还在当前区间内。写代码之前先把这个不变式写出来，自然就知道while条件该用<=还是<，right该怎么更新。这个习惯对后面二叉树、更复杂的查找题都极其有用。

移除元素和平方数组训练的是“指针语义”。每个指针都有明确分工：slow是写指针，fast是读指针；i和j分别是还没处理的左右边界。写代码之前先问自己：每个指针代表什么？什么条件下移动？循环结束条件是什么？想清楚了再动手，代码基本一遍过。

5.2 第一天的坑，汇总成一张表

5.3 关于训练节奏的个人体会

除非你天赋异禀，否则第一天的“看懂”根本不等于“会写”。我自己的做法是所谓的三遍法：先看一遍解析，合上答案自己默写一次，卡住的地方做个标记；过半天完全不看答案再独立写一遍；再过一天把易错点写进笔记，顺便把变体题做一遍。这个节奏在第一周尤其重要，因为数组是所有数据结构里最不需要“背”的一类，只要原理通了，写法翻来覆去就那么几种。

另外我想说一个很多初学者会忽略的点：别急着赶进度。第一天四道题，听起来量很少，但每一道都值得把暴力解、最优解、边界情况、复杂度分析写全。后面字符串、链表、双指针进阶题目，很多都是这几道题的组合变形。地基打不牢，后面容易出现“看着会做、一写就错”的老大难问题。

最后分享一个小技巧：二分查找写完，一定要用长度为1和长度为2的数组各测一遍，尤其是target取右端点。这个习惯我在之后每一个写二分的日子都在用，基本能保证边界一把过。DAY1到这里，剩下的就是动手写了——把代码敲出来，比看十篇笔记都有用。