当前位置：首页 > news >正文

【算法日记16】LeetCode 283. 移动零：O(N) 双指针魔法 (附可视化动画源码)

news 2026/7/8 1:26:55

📍 题目背景

今天我们来拆解 LeetCode 上一道非常经典的数组操作题：[283. 移动零]。这道题看似简单，但极其考验对数组底层操作的理解。很多新手在做这道题时，都会掉进“迭代器失效”或“时间复杂度爆炸”的陷阱里。

【题目描述】给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。请注意，必须在不复制数组的情况下原地对数组进行操作。

【示例】

输入:nums =[0,1,0,3,12]输出:[1,3,12,0,0]

💣 新手常见误区：边遍历边修改

很多人的第一直觉是：遍历数组，遇到0就把它删掉（例如用erase），然后在数组末尾追加（push_back）一个0。

为什么这个想法在 C++ 中非常危险？

时间复杂度爆炸：数组在内存中是连续存储的。每次在中间删除一个元素，它后面的所有元素都要往前挪动一格。如果有很多个0，时间复杂度会直接退化成极其缓慢的 $O(N^2)$。
迭代器失效：如果你使用for(auto i : nums)遍历数组，同时又在循环内部修改数组的长度（push_back），会导致程序彻底混乱甚至崩溃。

✨ 核心破题逻辑：双指针法 (Two Pointers)

既然不能随便删除元素，我们该怎么做？这就要请出数组操作的神级套路——双指针法！我们可以设立两个指针：探路者fast和收纳箱slow。

执行逻辑三步曲：

fast指针负责探路：遍历整个数组，遇到0直接无视跳过。
slow指针负责收纳：只要fast遇到了“非 0 数字”，就把这个数字一把塞进slow指向的位置，然后slow往后挪一格，准备接下一个。
末尾补 0：当fast跑完整个数组时，所有的非零数字都已经被紧凑地挤到了最前面。此时slow指针所在的位置，一直到数组末尾的空位，全部填成0即可！

这种方法无论数组多长，永远只需要扫两遍，时间复杂度是极其完美的 $O(N)$，并且是原地修改，空间复杂度为 $O(1)$。

💻 C++ 满分 AC 代码

#include <iostream> #include <vector> using namespace std; class Solution { public: void moveZeroes(vector<int>& nums) { // slow 就像是一个“收纳箱”的指针，专门记录下一个“非零数字”该放的位置 int slow = 0; // 1. 第一遍扫描：把所有【非零数字】全部按顺序往前挤 for (int fast = 0; fast < nums.size(); fast++) { if (nums[fast] != 0) { nums[slow] = nums[fast]; // 把非零数字存进收纳箱 slow++; // 收纳箱的位置往后挪一格 } } // 2. 第二步：收纳箱存完非零数字后，后面的空位全填上 0 就行啦！ for (int i = slow; i < nums.size(); i++) { nums[i] = 0; } } };

🎁 独家彩蛋：双指针运行动画 (前端源码)

为了让大家更加直观地理解fast和slow是如何绝妙配合的，我用 HTML + TailwindCSS + 原生 JS 写了一个轻量级的交互式动画。大家可以直接将下面这段代码保存为index.html并在浏览器中打开，亲眼见证双指针的魔法！

<!DOCTYPE html> <html lang="zh-CN"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>双指针魔法：移动零</title> <script src="[https://cdn.tailwindcss.com](https://cdn.tailwindcss.com)"></script> <style> .cell-transition { transition: all 0.3s ease-in-out; } .highlight-fast { box-shadow: 0 0 15px rgba(239, 68, 68, 0.6); border-color: #ef4444; } .highlight-slow { box-shadow: 0 0 15px rgba(59, 130, 246, 0.6); border-color: #3b82f6; } .highlight-both { box-shadow: 0 0 15px rgba(168, 85, 247, 0.6); border-color: #a855f7; background-color: #faf5ff; } </style> </head> <body class="bg-gray-50 min-h-screen flex flex-col items-center justify-center p-4 font-sans text-gray-800"> <div class="max-w-3xl w-full bg-white rounded-2xl shadow-xl overflow-hidden"> <div class="bg-indigo-600 text-white p-6 text-center"> <h1 class="text-3xl font-bold mb-2">🚗 双指针魔法：移动零</h1> <p class="text-indigo-200">LeetCode 283. 动态图解演示 (O(N) 时间复杂度)</p> </div> <div class="p-8"> <div class="bg-blue-50 border-l-4 border-blue-500 p-4 rounded-r-lg mb-10 h-24 flex items-center"> <p id="message-box" class="text-lg font-medium text-blue-800">准备开始！点击“下一步”或“自动播放”观察指针的移动。</p> </div> <div class="flex flex-wrap justify-center gap-4 mb-16" id="array-container"></div> <div class="flex justify-center gap-4"> <button id="btn-reset" class="px-6 py-2 bg-gray-200 hover:bg-gray-300 text-gray-700 font-semibold rounded-full">🔄 重置</button> <button id="btn-step" class="px-6 py-2 bg-indigo-500 hover:bg-indigo-600 text-white font-semibold rounded-full shadow-md">👣 下一步</button> <button id="btn-play" class="px-6 py-2 bg-green-500 hover:bg-green-600 text-white font-semibold rounded-full shadow-md">▶️ 自动播放</button> </div> <div class="mt-8 flex justify-center gap-8 text-sm font-medium text-gray-500"> <div class="flex items-center gap-2"><span class="w-3 h-3 rounded-full bg-red-500"></span> fast (探路者)</div> <div class="flex items-center gap-2"><span class="w-3 h-3 rounded-full bg-blue-500"></span> slow (收纳箱)</div> </div> </div> </div> <script> const initialArray = [0, 1, 0, 3, 12]; let currentFrameIndex = 0, isPlaying = false, playInterval; const frames = []; function generateFrames() { let arr = [...initialArray], slow = 0; frames.push({arr: [...arr], fast: 0, slow: 0, msg: "【第 1 阶段】准备开始！fast 负责探路寻找非零数，slow 负责标记存放位置。"}); for (let fast = 0; fast < arr.length; fast++) { if (arr[fast] !== 0) { frames.push({arr: [...arr], fast: fast, slow: slow, msg: `fast 找到了非零数字 <b>${arr[fast]}</b>！准备把它存入 slow 的位置。`}); arr[slow] = arr[fast]; frames.push({arr: [...arr], fast: fast, slow: slow, msg: `复制成功！现在 slow 可以向后移动一格，准备接下一个数字。`}); slow++; } else { frames.push({arr: [...arr], fast: fast, slow: slow, msg: `fast 指向了 0，这不是我们要找的，直接无视并跳过！`}); } } frames.push({arr: [...arr], fast: -1, slow: slow, msg: "【第 2 阶段】探路结束！非零数字都排好了。现在把 slow 及后面的空位全部填成 0。"}); for (let i = slow; i < arr.length; i++) { arr[i] = 0; frames.push({arr: [...arr], fast: -1, slow: i, msg: `把位置 ${i} 填上 0。`}); } frames.push({arr: [...arr], fast: -1, slow: -1, msg: "🎉 大功告成！所有的 0 都被完美地挤到末尾啦！时间复杂度 O(N)。"}); } function render() { const frame = frames[currentFrameIndex]; document.getElementById('message-box').innerHTML = frame.msg; const container = document.getElementById('array-container'); container.innerHTML = ''; frame.arr.forEach((val, i) => { const wrapper = document.createElement('div'); wrapper.className = 'flex flex-col items-center w-16 md:w-20'; const sLabel = document.createElement('div'); sLabel.className = 'h-6 text-sm font-bold text-blue-500 mb-1'; sLabel.innerHTML = frame.slow === i ? '↓ slow' : ''; const box = document.createElement('div'); let classes = 'w-16 h-16 md:w-20 md:h-20 flex items-center justify-center text-2xl font-bold border-4 rounded-xl cell-transition bg-white text-gray-800 '; if (frame.fast === i && frame.slow === i) classes += 'highlight-both'; else if (frame.fast === i) classes += 'highlight-fast'; else if (frame.slow === i) classes += 'highlight-slow'; else { classes += 'border-gray-200'; if(val === 0 && frame.fast === -1) classes += ' text-gray-400 bg-gray-50'; } box.className = classes; box.innerText = val; const fLabel = document.createElement('div'); fLabel.className = 'h-6 text-sm font-bold text-red-500 mt-1'; fLabel.innerHTML = frame.fast === i ? '↑ fast' : ''; wrapper.appendChild(sLabel); wrapper.appendChild(box); wrapper.appendChild(fLabel); container.appendChild(wrapper); }); document.getElementById('btn-step').disabled = currentFrameIndex >= frames.length - 1; } document.getElementById('btn-step').addEventListener('click', () => { if (currentFrameIndex < frames.length - 1) { currentFrameIndex++; render(); } }); document.getElementById('btn-reset').addEventListener('click', () => { currentFrameIndex = 0; if(isPlaying) togglePlay(); render(); }); document.getElementById('btn-play').addEventListener('click', togglePlay); function togglePlay() { const btn = document.getElementById('btn-play'); if (isPlaying) { clearInterval(playInterval); btn.innerHTML = '▶️ 自动播放'; isPlaying = false; } else { if(currentFrameIndex >= frames.length - 1) currentFrameIndex = 0; btn.innerHTML = '⏸️ 暂停播放'; isPlaying = true; playInterval = setInterval(() => { if (currentFrameIndex < frames.length - 1) { currentFrameIndex++; render(); } else togglePlay(); }, 1000); } } generateFrames(); render(); </script> </body> </html>

💡 总结：双指针是处理数组原地操作的一件神兵利器。无论是“移除元素”、“移动零”，还是“删除有序数组中的重复项”，只要牢记“探路者与收纳箱”的配合逻辑，一切都能迎刃而解！

查看全文

http://www.jsqmd.com/news/1144651/