为什么LintCode解法近半都是O(1)空间289道C题时间复杂度优化深度解析【免费下载链接】LintCode C11 Solutions of All 289 LintCode Problems (No More Updates)项目地址: https://gitcode.com/gh_mirrors/lintc/LintCode这是GitHub 加速计划 / lintc / LintCode项目一套用 C11 完成的全部 289 道 LintCode 算法题解法库。如果你打开 README.md 扫一眼复杂度表格会注意到一个现象——O(1) 空间解法多达 160 个接近总量的一半。为什么这么多 LintCode 解法几乎全是 O(1) 空间本文带你从双指针、快慢指针到 Morris 遍历、滚动数组看懂 LintCode O(1) 空间解法背后的 4 个核心套路以及时间复杂度优化和空间复杂度优化如何相互成就。先上数据O(1) 空间解法到底占了多少把 README.md 中所有题目标注的 Space 列统计一遍结果非常直观空间复杂度数量典型题目特点O(1)160二分查找、旋转数组、多数元素原地操作只用常量个变量O(log n) ~ O(h)40排序链表、BST 中序迭代递归调用栈或树高O(n)60前缀和、哈希表、BFS 队列需要额外数组/队列O(n²) ~ O(mn)10爆气球、打乱字符串二维 DP 状态表划重点LintCode 的 Array、Linked List、Binary Search、Math 四大分类几乎是 O(1) 空间的重灾区——二分查找类 17 题中16 题是 O(1) 空间链表分类 25 题中23 题是 O(1) 空间。这不是巧合而是题解作者刻意追求最优空间的风格选择。下面拆解背后的 4 个核心技术。️套路一双指针 原地修改让 O(n) 空间凭空消失最朴素的做法往往是开一个新数组存结果O(n) 空间瞬间就有了。而 O(1) 空间的 LintCode 解法几乎都选择直接改写原数组3 Sum / 3 Sum ClosestC/3-sum.cpp、C/3-sum-closest.cpp排序后固定一个数左右两个指针向中间夹逼O(n²) 时间、O(1) 额外空间排序空间另计Move ZeroesC/move-zeroes.cpp慢指针记录非零区末尾快指针扫描一次遍历原地完成Partition Array / Sort ColorsC/partition-array.cpp荷兰国旗三指针一趟扫描完成分区本质用指针的相对位置关系代替已处理/未处理的边界记录把本来要花在辅助数组上的空间省成了几个整型变量。这也是为什么Two Pointers在 README 的 Tag 列里高频出现——它和时间复杂度 O(n) 优化、空间复杂度 O(1) 优化是同一枚硬币的两面。套路二快慢指针用速度差替代存储哈希表能判断链表有没有环但要 O(n) 空间。LintCode 的两个经典题给出了更优雅的答案Linked List Cycle / Cycle IIC/linked-list-cycle-ii.cpp慢指针每次走 1 步、快指针每次走 2 步相遇即有环相遇后一头回到起点、两者同速前进再相遇处就是环入口。全程只用 2 个指针变量O(n) 时间 O(1) 空间Nth to Last NodeC/nth-to-last-node-in-list.cpp先让头指针走 n-1 步再双指针同速前进一次遍历找出倒数第 n 个节点这类技巧的通用思想是当问题本质是距离/相遇时用指针移动代替历史记录。时间复杂度 O(n) 保持不变空间复杂度却从 O(n) 降到 O(1)。套路三Morris 遍历把栈藏进树的指针里树的遍历通常要 O(h) 栈空间。但 LintCode 的前/中/后序三兄弟C/binary-tree-preorder-traversal.cpp、C/binary-tree-inorder-traversal.cpp、C/binary-tree-postorder-traversal.cpp给出的首选解法都是Morris 遍历空间 O(1)。原理一句话利用叶子节点右孩子为空的闲置指针建立临时线索指回祖先。走到某节点时先找到左子树的最右节点中序前驱如果它的右指针为空就连向当前节点上架不为空说明回来过断开恢复原状下架再走右子树。时间复杂度优化看似每个节点可能被访问多次但所有临时指针总共只建立/拆除 2n 次总时间仍是 O(n)空间复杂度优化递归/迭代栈完全消失O(h) → O(1)同样的用输入结构本身做状态思路还出现在Copy List with Random PointerC/copy-list-with-random-pointer.cpp不用哈希表存原节点→克隆节点映射而是把克隆节点直接插到原节点后面三趟扫描完成深拷贝O(n) 时间 O(1) 空间不计新链表本身。套路四滚动数组与状态压缩DP 空间的瘦身术DP 天然是空间大户。LintCode 的动态规划章节展示了两种压法一维滚动Climbing StairsC/climbing-stairs.cpp只保留f[i-1]和f[i-2]两个变量循环滚动更新O(n) 时间 O(1) 空间同题还附了矩阵快速幂版本时间进一步压到O(log n)、空间仍是 O(1)——时间复杂度优化的天花板二维压一维Edit Distance / Longest Common SubsequenceC/edit-distance.cpp、C/longest-common-subsequence.cpp只依赖上一行状态空间从 O(m·n) 压到 O(min(m, n))前缀和 哈希Subarray SumC/subarray-sum.cpp用哈希表记录前缀和出现次数把 O(n²) 枚举优化到 O(n) 时间——空间换时间的典型反例时间复杂度优化与空间复杂度优化为什么常常一体两面复盘 160 个 O(1) 空间解法规律很清晰原地改写数组/链表题指针定位代替额外容器时间不升、空间直降利用问题几何性质环形链表、山峰元素数学关系代替枚举存储借用输入结构的冗余位Morris 遍历临时线索用完即恢复状态压缩DP 题只保留状态转移真正依赖的历史当然也有必须付出空间的题C/subarray-sum.cpp 的前缀和哈希、C/sliding-window-maximum.cpp 的单调队列 O(k)、C/burst-balloons.cpp 的 O(n²) 区间 DP——当状态依赖关系无法压缩时空间复杂度优化的边界就到了此时更值得投入的是时间复杂度优化例如把 O(n³) 枚举优化到 O(n²)。新手学习路线按空间标签刷 LintCode给初学者的建议路线均可在 README.md 中按标题直接定位解法源码见 C/ 目录第一步 · 二分查找C/search-in-rotated-sorted-array.cpp、C/first-bad-version.cpp——体会指针夹逼带来的 O(log n) 时间 O(1) 空间第二步 · 双指针C/move-zeroes.cpp、C/trapping-rain-water.cpp——建立原地操作的空间意识第三步 · 链表C/reverse-linked-list.cpp、C/linked-list-cycle-ii.cpp——掌握快慢指针第四步 · 滚动 DPC/house-robber.cpp、C/best-time-to-buy-and-sell-stock-ii.cpp——学会状态压缩进阶 · Morris 遍历C/binary-tree-inorder-traversal.cpp——挑战 O(1) 空间遍历的极限⚠️ 注意一个常见误区O(1) 空间指辅助空间。像 Morris 前序遍历的返回值 vector 本身占 O(n)但求解过程不新增容器所以标注为 O(1)。每个解法文件头部都有// Time: O(...) // Space: O(...)注释可作为标注规范参考。总结LintCode 解法近半是 O(1) 空间不是运气而是方法论双指针原地修改、快慢指针、Morris 临时线索、滚动状态压缩——4 个套路覆盖了绝大多数 O(1) 空间解法。它们共同说明了一件事时间复杂度优化和空间复杂度优化往往共享同一个洞察——找到问题中可复用的结构就地利用而不是另起炉灶。想深入研读从 README.md 的分类目录入手每个题目都标注了 Time / Space / 难度 / 技巧标签配套的完整 C11 源码放在 C/ 目录下部分题目另有 Python/ 与 Java/ 版本对照MIT 协议授权LICENSE.md。动手读完这 289 个解法你对空间复杂度的理解会非常不一样。【免费下载链接】LintCode C11 Solutions of All 289 LintCode Problems (No More Updates)项目地址: https://gitcode.com/gh_mirrors/lintc/LintCode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考