算法训练营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重新纳入搜索造成死循环。为了直观直接看对比表区间写法while条件left更新right更新区间内有没有right左闭右闭left rightleft mid 1right mid - 1有左闭右开left rightleft mid 1right mid没有2.2 完整代码与手推过程704题先给C版本class Solution { public: int search(vectorint 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 7left 0, right 6, mid 3nums[3] 7正好命中返回3一次就找到了。再走一个不命中的过程target 8关键看区间怎么收拢left 0, right 6, mid 3nums[3] 7 8所以left 4left 4, right 6, mid 5nums[5] 11 8所以right 4left 4, right 4, mid 4nums[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 - 1left 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 0nums[0] 1 3left 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(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; } };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 0nums[0] 3等于val跳过fast 1nums[1] 2不等于valnums[0] 2slow变为1fast 2nums[2] 2不等于valnums[1] 2slow变为2fast 3nums[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: vectorint sortedSquares(vectorint nums) { int n nums.size(); vectorint 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)²16j 4对应10²100100更大res[4]100j变3k变3i 0对应16j 3对应3²916更大res[3]16i变1k变2i 1对应(-1)²1j 3对应99更大res[2]9j变2k变1i 1对应1j 2对应01更大res[1]1i变2k变0i 2对应0j 2对应0相等时走进else分支res[0]0j变1i 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 第一天的坑汇总成一张表题型常见错误正确做法二分查找while条件用错漏查右端点左闭右闭用left right左闭右开用left right二分查找right更新不减1导致死循环左闭右闭写right mid - 1左闭右开写right mid移除元素忘记返回slow作为新长度先看清函数签名返回值必须给移除元素用erase代替原地覆盖理解erase底层也是移动练题阶段别用来偷懒平方数组先平方再sort观察“最大只在两端”用对向双指针优化到O(n)5.3 关于训练节奏的个人体会除非你天赋异禀否则第一天的“看懂”根本不等于“会写”。我自己的做法是所谓的三遍法先看一遍解析合上答案自己默写一次卡住的地方做个标记过半天完全不看答案再独立写一遍再过一天把易错点写进笔记顺便把变体题做一遍。这个节奏在第一周尤其重要因为数组是所有数据结构里最不需要“背”的一类只要原理通了写法翻来覆去就那么几种。另外我想说一个很多初学者会忽略的点别急着赶进度。第一天四道题听起来量很少但每一道都值得把暴力解、最优解、边界情况、复杂度分析写全。后面字符串、链表、双指针进阶题目很多都是这几道题的组合变形。地基打不牢后面容易出现“看着会做、一写就错”的老大难问题。最后分享一个小技巧二分查找写完一定要用长度为1和长度为2的数组各测一遍尤其是target取右端点。这个习惯我在之后每一个写二分的日子都在用基本能保证边界一把过。DAY1到这里剩下的就是动手写了——把代码敲出来比看十篇笔记都有用。