题目背景今天咱们来挑战算法面试中极其高频、让无数新手痛不欲生的经典大题[15. 三数之和]。 这道题是经典的“双指针”进阶题如果用三个for循环暴力破解不仅时间复杂度会飙升到 $O(N^3)$ 直接超时更痛苦的是题目要求结果中不能包含重复的三元组在乱序数组里去重简直是地狱级难度。【题目描述】给你一个包含 $n$ 个整数的数组nums判断nums中是否存在三个元素 $a$$b$$c$ 使得 $a b c 0$ 请你找出所有和为 0 且不重复的三元组。【示例】输入:nums [-1,0,1,2,-1,-4]输出:[[-1,-1,2],[-1,0,1]]✨ 核心破题逻辑降维打击 (排序 双指针)既然找 3 个数字太难不如我们把它降维固定 1 个数再去用“左右指针”找另外 2 个数破题四步走先排个序核心灵魂这是降维打击的基础排序后相同的数字就会挨在一起这让我们后面能够轻松“去重”。而且只有数组有序了左右指针才知道该往哪边走。固定“大哥” (i)用一个for循环从左到右遍历数组每次选定一个nums[i]作为“大哥”。派出左右“小弟” (left,right)在“大哥”右边的区间里派left站在最左边right站在最右边开始向中间夹击寻找如果总和 0说明数字太大了右小弟right往左走一步找更小的数。如果总和 0说明数字太小了左小弟left往右走一步找更大的数。如果总和 0恭喜找到一组答案记录下来疯狂去重精髓遇到和上一次完全相同的数字直接跳过绝不干重复的活儿 史上最烦人的陷阱去重这道题 80% 的报错都来自于去重没写好。比如数组排序后是[-1, -1, -1, 0, 1, 1]如果不去重你找出来的答案全是重复的[-1, 0, 1]。去重必须设下“两道门禁”大哥去重如果当前的nums[i]和上一个nums[i-1]是一样的说明这个数字当大哥的组合已经被找过了直接continue跳过。小弟去重当左右小弟找到一组0后left要看看右边是不是双胞胎nums[left] nums[left1]right要看看左边是不是双胞胎。如果是果断跨过去 C 满分 AC 代码掌握了上面的逻辑这套双指针组合拳打出来极其优雅#include iostream #include vector #include algorithm using namespace std; class Solution { public: vectorvectorint threeSum(vectorint nums) { vectorvectorint res; // 第一步排序降维打击的基础 sort(nums.begin(), nums.end()); // 第二步固定大哥 (nums[i]) for(int i 0; i nums.size(); i) { // 【究极优化】大哥都大于0了后面的小弟肯定更大绝对凑不出0直接下班 if(nums[i] 0) break; // 【大哥去重】遇到双胞胎大哥直接跳过 if(i 0 nums[i] nums[i-1]) continue; // 第三步派出左右小弟开始夹击 int left i 1; int right nums.size() - 1; while(left right) { int sum nums[i] nums[left] nums[right]; if(sum 0) { // 找到一组记录下来 res.push_back({nums[i], nums[left], nums[right]}); // 【小弟去重】跨过一模一样的双胞胎小弟 while(left right nums[left] nums[left1]) left; while(left right nums[right] nums[right-1]) right--; // 跨过去后各自再往前走一步寻找下一组可能 left; right--; } else if(sum 0) { left; // 太小了左边往右走找大点儿的 } else { right--; // 太大了右边往左走找小点儿的 } } } return res; } };【复杂度分析】时间复杂度$O(N^2)$。排序的时间是 $O(N \log N)$。外层遍历大哥需要 $O(N)$内层两个小弟相向而行遍历剩下的数组也需要 $O(N)$。所以整体是 $O(N \log N N^2)$也就是 $O(N^2)$。空间复杂度$O(1)$ 或 $O(\log N)$。除了存储答案的数组我们只用了几个指针变量。实际的空间消耗主要取决于语言底层sort排序算法所占用的栈空间。 独家彩蛋双指针运行 3D 动画 (前端源码)这道题的去重逻辑光看文字很容易晕。为了直观感受我用 HTML TailwindCSS JS 写了一个轻量级的交互式动画。 大家可以直接将下面这段代码保存为index.html并在浏览器中打开亲眼见证指针是怎么夹击和跳过去重的!DOCTYPE html html langzh-CN head meta charsetUTF-8 meta nameviewport contentwidthdevice-width, initial-scale1.0 title双指针魔法三数之和/title script src[https://cdn.tailwindcss.com](https://cdn.tailwindcss.com)/script style .cell-transition { transition: all 0.4s cubic-bezier(0.4, 0, 0.2, 1); } .highlight-i { box-shadow: 0 0 15px rgba(168, 85, 247, 0.7); border-color: #a855f7; background-color: #faf5ff; } .highlight-left { box-shadow: 0 0 15px rgba(59, 130, 246, 0.7); border-color: #3b82f6; background-color: #eff6ff; } .highlight-right { box-shadow: 0 0 15px rgba(239, 68, 68, 0.7); border-color: #ef4444; background-color: #fef2f2; } .highlight-found { box-shadow: 0 0 20px rgba(34, 197, 94, 0.9); border-color: #22c55e; background-color: #f0fdf4; transform: scale(1.1); z-index: 10; } .highlight-skip { border-color: #9ca3af; background-color: #f3f4f6; opacity: 0.7; } /style /head body classbg-gray-100 min-h-screen flex flex-col items-center justify-center p-4 font-sans text-gray-800 div classmax-w-4xl w-full bg-white rounded-2xl shadow-2xl overflow-hidden div classbg-gradient-to-r from-purple-600 to-indigo-600 text-white p-6 text-center h1 classtext-3xl font-bold mb-2️‍♂️ 左右指针魔法三数之和 (3Sum)/h1 p classtext-indigo-100LeetCode 15. 排序 固定一端 双指针夹击/p /div div classp-8 div classbg-blue-50 border-l-4 border-blue-500 p-5 rounded-r-xl mb-10 min-h-[100px] flex items-center shadow-sm p idmessage-box classtext-lg font-medium text-blue-900 leading-relaxed准备开始点击“下一步”或“自动播放”观察指针是如何配合的。/p /div div classflex flex-wrap justify-center gap-4 mb-16 idarray-container/div div classmb-8 text-center min-h-[40px] span classtext-gray-500 font-semibold mr-2已找到的不重复三元组/span span idresults-box classtext-green-600 font-bold text-xl[]/span /div div classflex justify-center gap-4 button idbtn-reset classpx-6 py-2.5 bg-gray-200 hover:bg-gray-300 text-gray-700 font-semibold rounded-full transition-colors shadow 重置/button button idbtn-step classpx-6 py-2.5 bg-indigo-500 hover:bg-indigo-600 text-white font-semibold rounded-full shadow-md transition-colors transform hover:scale-105 下一步/button button idbtn-play classpx-6 py-2.5 bg-green-500 hover:bg-green-600 text-white font-semibold rounded-full shadow-md transition-colors transform hover:scale-105▶️ 自动播放/button /div div classmt-10 flex flex-wrap justify-center gap-6 text-sm font-bold text-gray-600 bg-gray-50 p-4 rounded-xl div classflex items-center gap-2span classw-4 h-4 rounded-md border-2 border-purple-500 bg-purple-100/span i (大哥)/div div classflex items-center gap-2span classw-4 h-4 rounded-md border-2 border-blue-500 bg-blue-100/span left (左小弟)/div div classflex items-center gap-2span classw-4 h-4 rounded-md border-2 border-red-500 bg-red-100/span right (右小弟)/div /div /div /div script const initialArray [-1, 0, 1, 2, -1, -4]; let currentFrameIndex 0, isPlaying false, playInterval, frames []; function generateFrames() { frames []; let original [...initialArray]; frames.push({ arr: original, i: -1, left: -1, right: -1, msg: 初始数组乱序无法直接查找。第一步先排序 }); let arr [...original].sort((a, b) a - b); frames.push({ arr: [...arr], i: -1, left: -1, right: -1, msg: 第一步完成从小到大排好队这是左右夹击和跳过重复数字的基础。 }); let results []; for (let i 0; i arr.length - 2; i) { if (arr[i] 0) { frames.push({ arr: [...arr], i: i, left: -1, right: -1, msg: 大哥 bi ${arr[i]}/b 已经大于0三个正数相加不可能等于0直接提前下班 }); break; } if (i 0 arr[i] arr[i - 1]) { frames.push({ arr: [...arr], i: i, left: -1, right: -1, skipI: true, msg: 触发【大哥去重魔法】跳过相同的数字。 }); continue; } let left i 1, right arr.length - 1; frames.push({ arr: [...arr], i: i, left: left, right: right, msg: 固定大哥 bi ${arr[i]}/b派出小弟准备夹击 }); while (left right) { let sum arr[i] arr[left] arr[right]; let sumText (${arr[i]}) (${arr[left]}) (${arr[right]}) b${sum}/b; if (sum 0) { results.push([${arr[i]}, ${arr[left]}, ${arr[right]}]); frames.push({ arr: [...arr], i: i, left: left, right: right, found: true, results: [...results], msg: 太棒了${sumText}。凑齐 0 啦 }); let startLeft left, startRight right; while (left right arr[left] arr[left 1]) left; while (left right arr[right] arr[right - 1]) right--; if (left ! startLeft || right ! startRight) { frames.push({ arr: [...arr], i: i, left: left, right: right, msg: 触发【小弟去重魔法】果断跨过重复数字 }); } left; right--; } else if (sum 0) { frames.push({ arr: [...arr], i: i, left: left, right: right, msg: 总和${sumText} 0。太小啦左小弟往右挪一步。 }); left; } else { frames.push({ arr: [...arr], i: i, left: left, right: right, msg: 总和${sumText} 0。太大啦右小弟往左挪一步。 }); right--; } } } frames.push({ arr: [...arr], i: -1, left: -1, right: -1, results: [...results], msg: 搜索彻底结束时间复杂度 O(N²)。 }); } function render() { const frame frames[currentFrameIndex]; document.getElementById(message-box).innerHTML frame.msg; if (frame.results) document.getElementById(results-box).innerHTML frame.results.join(, ); else if (currentFrameIndex 0) document.getElementById(results-box).innerHTML []; const container document.getElementById(array-container); container.innerHTML ; frame.arr.forEach((val, index) { const wrapper document.createElement(div); wrapper.className flex flex-col items-center w-14 md:w-20; const topLabel document.createElement(div); topLabel.className h-6 text-sm font-bold text-purple-600 mb-1; topLabel.innerHTML frame.i index ? ↓ i : ; const box document.createElement(div); let boxClasses w-14 h-14 md:w-20 md:h-20 flex items-center justify-center text-xl md:text-2xl font-bold border-4 rounded-xl cell-transition text-gray-800 bg-white border-gray-200 ; if (frame.found (frame.i index || frame.left index || frame.right index)) boxClasses highlight-found; else if (frame.skipI frame.i index) boxClasses highlight-skip; else if (frame.i index) boxClasses highlight-i; else if (frame.left index) boxClasses highlight-left; else if (frame.right index) boxClasses highlight-right; box.className boxClasses; box.innerText val; const bottomLabel document.createElement(div); bottomLabel.className h-6 text-sm font-bold mt-1; if (frame.left index frame.right index) { bottomLabel.innerHTML ↑ L/R; bottomLabel.classList.add(text-gray-600); } else if (frame.left index) { bottomLabel.innerHTML ↑ left; bottomLabel.classList.add(text-blue-600); } else if (frame.right index) { bottomLabel.innerHTML ↑ right; bottomLabel.classList.add(text-red-600); } wrapper.appendChild(topLabel); wrapper.appendChild(box); wrapper.appendChild(bottomLabel); container.appendChild(wrapper); }); document.getElementById(btn-step).disabled currentFrameIndex frames.length - 1; document.getElementById(btn-step).className currentFrameIndex frames.length - 1 ? px-6 py-2.5 bg-gray-300 text-gray-500 font-semibold rounded-full cursor-not-allowed shadow : px-6 py-2.5 bg-indigo-500 hover:bg-indigo-600 text-white font-semibold rounded-full shadow-md transition-colors transform hover:scale-105; } 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 playBtn document.getElementById(btn-play); if (isPlaying) { clearInterval(playInterval); playBtn.innerHTML ▶️ 自动播放; playBtn.classList.replace(bg-yellow-500, bg-green-500); playBtn.classList.replace(hover:bg-yellow-600, hover:bg-green-600); isPlaying false; } else { if(currentFrameIndex frames.length - 1) currentFrameIndex 0; playBtn.innerHTML ⏸️ 暂停播放; playBtn.classList.replace(bg-green-500, bg-yellow-500); playBtn.classList.replace(hover:bg-green-600, hover:bg-yellow-600); isPlaying true; playInterval setInterval(() { if (currentFrameIndex frames.length - 1) { currentFrameIndex; render(); } else { togglePlay(); } }, 1500); } } generateFrames(); render(); /script /body /html 总结从暴力 $O(N^3)$ 到优雅的 $O(N^2)$中间隔着的就是排序和双指针。尤其是“去重”逻辑充分展现了在编码时考虑边界条件Edge Cases的严谨性。拿下这道题面试中遇到任何“N数之和”的问题你都可以自信应对