1. 先搞清楚这道题到底在问什么1.1 题目描述逐句拆解题目编号 26题名“删除有序数组中的重复项”是我见过最适合零基础入门“双指针法”的一道题没有之一。它不涉及高深的数据结构不考复杂的数学推导核心逻辑用两句话就能讲完给你一个按非递减顺序排列的数组你需要原地删除重复出现的元素让每个元素只出现一次然后返回新的数组长度。注意几个关键词一个都不能漏。第一个是“有序”。数组已经排好序了意味着所有相同的值会连在一起。这一点直接决定了我们能用非常轻量的方式去重而不是动用哈希表之类的额外结构。第二个是“原地”。题目原话是不会使用额外数组空间且必须通过修改输入数组来实现。这不仅是这道题的限制也是面试里常考的工程意识能在原数组上操作就不要新开空间因为实际工作中数据的搬移和内存开销往往比逻辑本身更值钱。第三个是“返回新长度”。它不是让你输出整个去重后的数组而是让你返回去重后还剩多少个元素。最后平台验证时会读取原数组前新长度个元素检查是否和预期一致。也就是说数组的前半段必须是无重复的后半段残留什么值都不重要。举个例子。输入数组是[1,1,2]去重后你应该把数组改成[1,2,2]或者[1,2,1]都可以只要前 2 个位置是1,2返回值是2就算通过。很多新手不知道这一点非要把数组后面多余的清掉其实完全没必要。1.2 为什么“有序”两个字是灵魂如果数组无序比如[2,1,2,1]你没法靠相邻比较来去重。要想高效去重常规做法是拿哈希集合记录出现过的元素遍历一遍没见过的就保留。这样时间复杂度也是 O(n)但需要 O(n) 的额外空间而且最终结果会天然变成“首次出现顺序”不再是原来的相对顺序。这道题刻意给了“有序”本质上是把难度降了一大截。因为值相等的元素一定排在相邻位置所以当你在数组中从左往右走的时候只需要时刻盯着“上一个保留的值”和“当前看到的值”是否相等就能判断当前值是不是重复项。这就像你在车站排队队伍里只有按身高从矮到高排好的人才可能相邻出现相同身高如果队伍乱站想找出相同身高就得来回比对。有序是双指针解法能够成立的前提。没有这个前提双指针就要换一种玩法或者干脆用其他数据结构。所以做题时不要把“有序”当成理所当然它是出题人埋下的最大提示。1.3 空间复杂度 O(1) 意味着什么常见的时间复杂度大家比较敏感空间复杂度经常被忽略。空间复杂度 O(1) 意思是除了必要的几个变量比如循环索引、计数器不能随着输入规模变大而申请额外的存储。你不能新建一个数组不能新建一个哈希表甚至连一个“新数组再复制回去”的缓冲都不行。那是不是除了输入数组本身什么都不能动也不是。你可以在原数组上自由修改可以申请几个固定大小的临时变量。所以最朴素的想法——“把不重复的元素挑出来放进新数组”——从根上就被拒绝了。这就倒逼我们想一个问题能不能让自己维护的“不重复区域”和原来的数组共用同一块内存当然可以这也是双指针法的精髓所在一个指针负责“写”一个指针负责“读”二者在原数组上前后脚移动写指针永远不会超过读指针所以覆盖掉的位置都是已经读过、不再需要的旧值安全又节省空间。2. 双指针思路是怎么一步步推出来的2.1 从暴力解法到双指针的演进很多零基础的同学看到题目第一反应是那我用两个循环遇到重复就删掉一个把后面的元素往前移。这个思路能通但时间复杂度是 O(n²)因为删除一个元素需要把后面的所有元素整体搬一次。如果数组有十万个元素且大部分是重复的操作次数非常恐怖。稍微好一点的做法是边遍历边把不重复元素往前面放。比如我准备一个变量k表示“当前已经确认的不重复元素个数”。从头开始扫描每遇到一个和上一个不重复的元素就把它放到数组第k个位置然后k加一。这不就是双指针吗是的这就是双指针。只不过很多初学者没有意识到所谓的双指针并不玄乎一个指针用来扫描原始数组我们可以叫它“快指针”或者fast另一个指针用来标记不重复区间的下一个写入位置我们可以叫它“慢指针”或者slow。两个指针都是从左往右移动所以整体只需要遍历一遍。这里有一个很关键的直觉如果数组有序那么“上一个不重复的元素”其实就是数组里已经在慢指针位置及其之前保存好的最后一个元素。因为我们每发现一个新值都会把它写到慢指针位置所以只要比较nums[fast]和nums[slow]是否相等就能知道当前值是不是已经出现过的重复项。注意这里的比较是“当前扫描值”和“最后一个保留值”比而不是和它前一个原始位置比。2.2 快慢指针的职责划分用一句话给两个指针划清职责slow指向结果数组的“下一个空位”。同时nums[slow]也代表当前已保留的最后一个不重复元素这个描述在初始状态下有点特殊需要结合代码理解。fast遍历原始数组负责发现“新的、和之前不同的元素”。更严谨的写法通常是这样def removeDuplicates(nums): if not nums: return 0 slow 0 for fast in range(1, len(nums)): if nums[fast] ! nums[slow]: slow 1 nums[slow] nums[fast] return slow 1初始化时slow 0意思是第一个元素一定保留不需要比较它自己。从fast 1开始扫描。当nums[fast]和nums[slow]相等时说明当前元素和最后一个保留元素重复什么都不做fast继续前进。当它们不相等时说明发现了一个新元素先把slow向后移一位再把当前值写进去。这里建议初学者先不要盯着slow和fast的位置死记硬背而是想象两个人在跑操slow是“成果验收员”只站到已经确认无重复的区域最后一个位置fast是“侦察兵”不断向前看新面孔看到新面孔就喊一声验收员往前挪一步把他收到队伍里。重复值再多验收员也纹丝不动。2.3 通过例子走一遍全过程纸上谈兵不够我们手动走一遍。假设输入是[0,0,1,1,1,2,2,3,3,4]。初始状态slow 0指向0fast 1指向第二个0。nums[1] nums[0]相等跳过。fast 2。nums[2] 1和nums[0] 0不等。slow变成1将nums[1]赋值为1。此时数组变成[0,1,1,1,1,2,2,3,3,4]。注意原数组第二个位置的1被覆盖成了1没变化但位置1现在代表结果区的第二个元素。fast 3nums[3] 1和nums[1] 1相等跳过。fast 4nums[4] 1和nums[1] 1相等跳过。fast 5nums[5] 2和nums[1] 1不等。slow变成2nums[2]被赋值2。以此类推最后slow停在9让我们数一下不重复元素是0,1,2,3,4共 5 个slow从 0 开始经历了 4 次不同写入slow最终等于4最后一个元素下标返回值是slow 1 5。细心的同学会发现slow指向的位置在循环中一直是“最后一个保留元素”但是当slow等于fast时赋值nums[slow] nums[fast]相当于自己给自己赋值完全无害。这也是双指针写法里最常见的隐蔽细节不要担心覆盖会破坏还没扫描到的数据因为slow永远小于等于fast它所覆盖的位置fast早就扫过了。3. 手写代码Python / C / Java 三种实现3.1 Python最贴近思路的写法Python 写这种题最直观因为你不需要纠结数组索引的类型声明也不需要手动管理内存。上面第 2 节的代码可以直接用但是我个人更喜欢另一种稍微泛化一点的写法因为它能顺带解决“保留 K 个元素”的进阶题后面会讲。def removeDuplicates(nums): if len(nums) 1: return len(nums) slow 1 for fast in range(1, len(nums)): if nums[fast] ! nums[slow - 1]: nums[slow] nums[fast] slow 1 return slow这里slow初始化为1表示“已经保留一个元素”比较对象是nums[slow - 1]。逻辑和前面等价但是初学阶段我个人更推荐第一种slow 0的写法因为nums[slow]就是“最后一个保留值”不需要多一个减一操作更容易理解。不过要注意如果nums是空列表第一种写法必须先判断if not nums第二种写法也要判断长度。边界条件永远不能丢。3.2 C注意边界与索引细节C 写法和 Python 几乎一一对应但有一些小细节值得警惕。class Solution { public: int removeDuplicates(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; } };这里最容易忽略的是nums.size()的返回类型是size_t无符号类型。如果nums为空nums.size() - 1就会变成巨大的数。所以在 C 里一定要先判空再谈后面的逻辑。另外fast nums.size()这个条件会隐式把fast转成无符号类型比较一般没问题但如果你不小心把fast声明成int且nums.size()是 0循环边界就会失控。稳妥做法是直接写for (int fast 1; fast (int)nums.size(); fast)或者开头判空后size一定大于等于 1其实不转也安全但养成显式转换的习惯可以少踩一些隐蔽的坑。还有一点C 的 vector 是引用传入你修改nums就是直接改原数组符合“原地”要求。如果你误把参数写成值传递那就等于复制了一份改了半天原数组没变平台判题直接失败。这是我见过不少新手在 C 里犯的低级错误。3.3 Java从语言角度看同样逻辑Java 的数组自带length属性不需要函数调用写法上比 C 清爽些。class Solution { public int removeDuplicates(int[] nums) { if (nums.length 0) return 0; int slow 0; for (int fast 1; fast nums.length; fast) { if (nums[fast] ! nums[slow]) { slow; nums[slow] nums[fast]; } } return slow 1; } }Java 和 C 的代码几乎一样因为核心逻辑就是数组下标操作。唯一要注意的可能是slow和slow在赋值场景下的区别。上面代码是先slow再nums[slow] nums[fast]如果你写成nums[slow] nums[fast]那么赋值用的下标是旧值slow写完后slow才加一。这两种写法效果不同但都能工作我们来验证一下如果slow是 0nums[slow] nums[fast]会把值写到下标 0然后slow变成 1。但第一个元素本来应该保留在 0如果当前fast扫描到的是第二个元素并且它和nums[0]不同你把它写到nums[0]就把原第一个元素覆盖了结果完全错了。所以先移动slow再写入是正确的先写后移只适用于slow表示“下一个写入位置”的写法。这两种风格初学者必须分清不然很容易写出逻辑相反的 bug。3.4 复杂度分析双指针解法的时空复杂度非常优秀。时间复杂度O(n)。fast指针从数组头走到尾每个元素只被访问一次slow指针虽然也会移动但它最多移动 n 次两个指针整体是线性扫描。空间复杂度O(1)。只用了常数个变量没有和 n 相关的额外空间。这种 O(n) 时间、O(1) 空间的解法已经是这道题的最优解。面试时你说出复杂度再解释清楚为什么不能更快基本就能过关。为什么时间不可能低于 O(n)因为至少要看一遍所有元素才能知道哪些重复就像不把整本书翻一遍你不可能知道哪些句子是抄的。4. 新手最容易踩的四个坑4.1 忘了处理空数组和长度为 1 的输入很多人在for循环里用了nums[slow]当nums为空时直接越界。比如写成slow 0 for fast in range(1, len(nums)): ...如果nums []len(nums)是 0range(1, 0)不会执行函数最后返回slow 1 1。原数组长度为 0你返回 1必然错误。所以要在一开始就判断if len(nums) 0: return 0对于长度 1 的数组range(1, 1)不执行返回slow 1 1正确所以不需要单独判断len(nums) 1但如果你使用的是slow 1的写法空数组依然要处理。总之一句话入口先判空永远不亏。4.2 覆盖顺序写反导致结果错乱这是最常见、也最隐蔽的一个坑。上面 Java 部分提到过nums[slow] nums[fast]和先slow再nums[slow] nums[fast]的区别。再举一个具体例子。假设数组是[1,2,3]我们希望保留全部。初始slow 0fast 1发现2 ! 1。如果写成nums[slow] nums[fast]会把2写到nums[0]数组变成[2,2,3]slow变成 1。接着fast 2发现3和nums[slow] nums[1] 2不等再nums[slow] nums[fast]把 3 写到nums[1]数组变成[2,3,3]返回slow 1 3。答案长度是 3但数组前三个元素是2,3,3丢了原来的 1判题就会失败。所以记住先把慢指针向后挪一挪把新元素放到空位上而不是覆盖掉当前最后一个保留值。4.3 把 nums[fast] 和 nums[fast - 1] 比较有些同学会觉得既然数组有序那直接判断当前元素和前一个元素相不相等不就行了我承认在这个具体的“删除所有重复项且保留一个”的场景下用nums[fast] ! nums[fast - 1]配合slow移动也能通过。但它有一个前提你比较的是原始数组中相邻元素而数组的前半部分可能已经被覆盖了。如果慢指针的写入位置正好落在fast - 1上就会用新值覆盖旧值导致后续比较出错。我不建议新手用这种“比较相邻”的写法。不是因为不能通过而是因为它破坏了双指针的通用性而且你很难解释清楚为什么在边界条件下依然正确。相比之下nums[fast] ! nums[slow]的语义是“当前元素是否和已保留的最后一个元素相同”无论数组前部分被覆盖成什么样都不影响判断。这才是可迁移的思路。为了让你彻底放心我们看一眼覆盖前后的状态slow永远指向“结果数组的末尾”它前面的位置都已经是不重复序列了。fast指向“待检查元素”。两个指针之间可能夹着很多已经被跳过的重复元素也可能紧挨着。慢指针写入的位置一定在fast之前或者等于fast不可能覆盖掉fast还没看的数据。这是双指针解法的安全基石。4.4 返回值写错长度不是索引因为slow是最后一个保留元素的下标所以返回值是slow 1。我见过有人直接返回slow结果所有测试用例都差 1。这个错误在样例[1,1,2]里特别容易发现slow最后等于 1返回 1 显然是错的应该是 2。还有人会写成slow 2把下标和长度混得更乱。建议你在纸上推演样例时刻意数一下结果数组里有多少个元素再回看slow的数字把“下标”和“长度”的换算刻在脑子里长度为 n 的数组最后一个元素下标是 n-1不重复元素个数 最后一个不重复元素下标 1。4.5 不知道如何验证答案在刷题平台上你提交后平台会自动验证。但本地调试时怎么确认自己改对了这里分享一个我自己常用的验证方法先调用函数得到返回值len然后打印数组的前len个元素再手动检查是否无重复且有序。nums [0,0,1,1,1,2,2,3,3,4] new_len removeDuplicates(nums) print(new_len) # 5 print(nums[:new_len]) # [0, 1, 2, 3, 4]如果打印结果不是[0, 1, 2, 3, 4]说明某个环节出了问题。另一个办法是用断言做自动化验证assert new_len 5 assert nums[:new_len] [0, 1, 2, 3, 4]养成写断言的习惯以后做更复杂的题也能快速定位问题。5. 进阶从“删除重复项”到“最多保留 K 个元素”5.1 通用解法的推导这道题还有一种更通用的双指针写法可以应对“有序数组中每个元素最多保留 k 个”的系列题目。核心思想是对于当前扫描到的元素nums[fast]只要它不等于位置slow - k上的元素就说明它在已保留序列中出现的次数还不到 k 个可以保留。以 k1 为例上面的写法就是nums[fast] ! nums[slow - 1]。当 k2也就是“删除有序数组中的重复项 II”某平台第 80 题题目要求每个元素最多出现两次这时候只需要把比较对象从slow - 1改成slow - 2def removeDuplicatesK(nums, k): if len(nums) k: return len(nums) slow k for fast in range(k, len(nums)): if nums[fast] ! nums[slow - k]: nums[slow] nums[fast] slow 1 return slow注意这里的slow初始化成k表示前 k 个元素天然保留。比如 k2数组前两个元素哪怕都是同一个值也允许保留。从第 3 个元素开始如果它和往前数第 2 个位置即slow - 2的值相同说明相同元素已经有 2 个了当前这个就要跳过否则就保留。这个通用模板非常实用。面试官让你先做第 26 题往往下一问就是第 80 题。如果你能当场把这个模板写出来并在复杂度分析后解释清楚为什么slow - k比较可以保证最多保留 k 个会是很强的加分项。5.2 第 80 题的思路延伸具体到“每个元素最多保留 2 次”我们走个例子[1,1,1,2,2,3]。k2slow2fast2nums[2]1nums[slow-2]nums[0]1相等说明 1 已经出现两次跳过。fast3nums[3]2nums[0]1不等保留nums[2]2slow3。fast4nums[4]2nums[slow-2]nums[1]1不等保留nums[3]2slow4。fast5nums[5]3nums[2]2不等保留nums[4]3slow5。返回 5去重后前五个元素是[1,1,2,2,3]正确。你会发现掌握了这个模板等于同时拿下了两道题。这也是为什么我强烈建议零基础同学不要只背代码而是理解slow和fast之间那个“距离”的含义slow - k指向的是结果序列中“从末尾往前数第 k 个”位置。这种面向区间边界的思考方式比死记硬背结论更有价值。5.3 双指针在真实场景中的映射你可能觉得这种数组去重题只存在于刷题平台实际工作里用不上。其实不然。很多工程场景都在做类似的事情比如数据清洗时需要从已排序的日志序列中剔除重复的id视频剪辑软件里需要把连续重复的关键帧去掉数据库的索引去重、流式数据处理里的“只保留最新值”等等本质上都是在一个可变的区间内维护“有效数据”的边界。双指针法特别适合那些“不能占用大量额外内存”的嵌入式环境或高并发服务。你不可能每来一条数据就新建一个结构去存而是要在原缓冲区上原地整理把有效数据往前压。这道题练的就是这个基础能力。我自己在写一个日志清理工具时就遇到过一个类似场景内存里有一个按时间排序的缓存数组需要把同一秒内重复的日志级别过滤掉只保留第一条。当时第一反应就是用双指针一个指针读一个指针写几行代码搞定既不用开辟新数组也不用list.remove这种 O(n) 操作反复搬移数据。刷题的价值正是在这种时刻体现出来的。最后再分享两个实战小技巧第一个技巧如果你在本地调试时总是分不清slow和fast的关系可以在循环里临时打印中间状态。比如def removeDuplicates(nums): if not nums: return 0 slow 0 for fast in range(1, len(nums)): if nums[fast] ! nums[slow]: slow 1 nums[slow] nums[fast] print(ffast{fast}, slow{slow}, nums_slice{nums[:slow1]}) return slow 1看到每一步数组前缀的变化会比盯着代码想一百遍更管用。等完全理解了再删掉打印语句。第二个技巧做这道题之前先自己把“数组”和“数组下标”这两个概念彻底搞清楚。很多零基础同学卡住不是因为双指针难而是不知道nums[slow]和slow是两回事。slow只是一个整数nums[slow]是这个整数对应位置的值。把它们的关系理清双指针就成功了一半。这道 26 题是我建议所有初学者在刷题早期就做的题目。它难度不高却把“原地修改”“指针思想”“边界处理”这三个最重要的基本功都覆盖了。认真吃透它后面再碰滑动窗口、链表快慢指针、或者更复杂的双指针题目你会发现很多思路都是相通的。希望这篇带刷笔记能帮你迈出第一步并且走得稳一点。