写 Java 算法这件事我见过太多人卡在同一个地方思路明明想通了代码一提交就是超时、就是答案对不上、就是跑大数据集时内存爆掉。问题往往不在算法本身而在 Java 这门语言自带的那些“隐性成本”——装箱、扩容、比较器契约、整型溢出、递归深度全是些你在纸上推公式时根本不会想到的东西。这篇就围绕算法Java这个主题把从“能把思路翻译成代码”到“代码能在真实约束下跑得动”中间那段路拆开讲清楚。适合两类人看一类是刚用 Java 刷题、发现同样的思路别人过自己不过的新手另一类是在工程里写业务算法、需要处理几十万条数据、对耗时和内存有实际要求的老手。我不会只给你模板重点是讲清楚每个选择背后的代价以及我实际踩过的那些坑。1. 先搞清楚Java 写算法慢的到底是语言还是思路很多人有个刻板印象觉得 Java 写算法天生比别的语言慢半拍。这个结论在十年前还有点道理现在基本站不住。JIT 编译之后的热点代码性能跟静态编译语言差不了多少。真正让 Java 算法代码跑不动的绝大多数是写代码时无意引入的额外开销而不是语言本身。我在实际项目里做过对照同一个图遍历逻辑一份用对象和集合写一份用数组和原始类型写数据规模到五十万节点时前者耗时是后者的六到八倍。算法复杂度完全一样差的全是常数因子。1.1 常数因子藏在哪些你看不见的地方先明确一个概念复杂度描述的是增长趋势不描述绝对耗时。O(n log n) 的排序n 等于十万的时候可能是 30 毫秒也可能是 300 毫秒取决于你在每次比较里干了什么。Java 里最常见的三个“隐性常数”来源我按影响从大到小排一下。第一是对象分配。每次new一个对象都要在堆上划一块内存对象头至少占 12 到 16 字节再加上字段对齐填充。一个只装两个 int 的小对象实际占用可能是 24 字节而两个裸 int 只有 8 字节。你在一个百万次循环里创建这种小对象就是几千万字节的垃圾GC 会被频繁唤醒。第二是装箱与拆箱。Integer、Long、Double这些包装类在集合里用起来很顺手但每次读写都可能触发一次对象创建或者一次方法调用。MapInteger, Integer存一百万个键值对内存占用大概是int[]数组方案的十倍以上访问速度也慢一截。第三是边界检查与虚方法调用。这个 Java 做得其实不错JIT 会做逃逸分析和内联但前提是代码结构足够简单。你如果在一个热循环里调用层层嵌套的接口方法内联就可能失败。提示判断自己的代码是不是被常数因子拖累了最简单的办法是把数据规模翻十倍跑一次。耗时如果涨了十倍左右说明是线性开销正常如果涨了三十倍甚至更多说明某处有超线性行为比如集合扩容、重复扫描、字符串拼接得重点查。1.2 四类容器的开销对照别再用错场景Java 集合框架用起来太方便了方便到很多人不去想它的底层。我整理了一张自己常用的对照表覆盖算法代码里出现频率最高的几种结构。表里的“随机访问”指的是按下标或按 key 直接取值的耗时量级。结构底层实现随机访问插入删除额外内存适合的场景int[]连续内存极快不支持几乎为零定长序列、DP 状态、邻接表头ArrayList动态数组极快尾部快中间慢少量需要动态增长且以读为主LinkedList双向链表很慢O(n)已知节点时快每节点约 24 字节频繁在两端增删的队列HashMap数组链表/红黑树快均摊 O(1)快每条约 32 到 48 字节计数、去重、索引映射TreeMap红黑树中等O(log n)中等每条约 40 字节需要有序遍历或范围查询PriorityQueue二叉堆数组仅堆顶 O(1)插入删除 O(log n)一个数组求 Top K、调度、最短路这张表最关键的一行其实是第一行。我在实际写算法时只要数据规模上万、并且元素类型是基本类型第一反应就是能不能用数组替代集合。数组没有扩容、没有装箱、没有迭代器JIT 对它最友好。代价是长度固定需要自己维护有效元素个数。这个代价在绝大多数算法场景里完全可以接受。1.3 什么时候该放弃“优雅”选“原始”这里要说一句可能不太讨喜的话算法代码和业务代码的评价标准是两套。业务代码讲究可读、可维护、可扩展算法代码讲究在约束内跑得动。你在工程里写一个订单匹配逻辑用Stream链式调用写出来很漂亮但如果这段逻辑要在一秒内处理十万条数据链式调用的中间集合创建开销可能就让你过不了线。我的判断标准是这样的如果这段代码的执行次数是常数级比如每次请求跑一次怎么写舒服怎么写如果执行次数跟数据规模成正比或者嵌套在循环里就必须回到原始写法。举个具体的例子下面这两段代码功能完全一样都是把列表里所有偶数挑出来求和。// 写法一链式可读性好 ListInteger nums getNumbers(); long sum nums.stream() .filter(n - n % 2 0) .mapToLong(Integer::longValue) .sum(); // 写法二原始循环 ListInteger nums getNumbers(); long sum 0L; for (int i 0, size nums.size(); i size; i) { int v nums.get(i); if ((v 1) 0) { sum v; } }数据量在几千以内两者差别你肉眼看不出来。数据量到百万级写法二通常快两到三倍内存峰值也低得多。这不是说链式写法不好而是说你得知道自己在付什么账然后在需要的时候能果断换回来。2. 输入输出与数据表示最容易被忽视的地基算法题或者数据处理任务第一道坎往往不是算法是数据怎么进来、怎么存。我见过不少人算法思路完全正确卡在输入解析上数据量一大用Scanner读进来就要好几秒直接超时。这块没什么技术含量但漏了就是漏了。2.1 快读模板什么时候必须自己写Java 标准输入有三个层次。Scanner最方便支持正则分隔、自动类型转换但内部做了大量字符串解析和模式匹配速度最慢读一百万个数大概要一到两秒。BufferedReader加StringTokenizer是中间方案读完整个缓冲区再切分速度能快十倍左右代码也不复杂。再往上就是自己从InputStream按字节读手写整型解析速度最快但代码丑、容易写错。我一般的做法是数据量在十万以内用BufferedReader那套就够了超过五十万直接上字节流快读。下面是我常用的字节流模板处理正负整数遇到非数字字符就跳过。import java.io.InputStream; import java.io.IOException; public class FastReader { private final InputStream in; private final byte[] buf new byte[1 16]; private int ptr 0; private int len 0; public FastReader(InputStream in) { this.in in; } private int read() throws IOException { if (ptr len) { len in.read(buf, 0, buf.length); ptr 0; if (len 0) { return -1; } } return buf[ptr]; } public int nextInt() throws IOException { int c read(); while (c ! -1 (c 0 || c 9) c ! -) { c read(); } boolean neg false; if (c -) { neg true; c read(); } int val 0; while (c 0 c 9) { val val * 10 (c - 0); c read(); } return neg ? -val : val; } }这段代码有几个细节值得说。缓冲区用 64KB是因为大多数场景下这个大小能覆盖一次系统调用的读取量再大收益递减。read()方法返回 -1 表示流结束主循环必须判断否则会死循环。负号单独处理因为-的 ASCII 码在数字范围之外混在循环里会让逻辑变乱。val * 10 (c - 0)这个写法依赖c - 0把字符转成数值比Character.getNumericValue快得多。注意这个模板只能读整数。如果输入里有小数或者字符串得另外处理。另外它假设输入格式规整遇到科学计数法或者千分位分隔符会读错。用之前先确认数据格式。2.2 整型边界int 和 long 的分水岭在哪int的范围是 -2147483648 到 2147483647大约正负二十一亿。这个数看着很大但在算法里特别容易撞上。几个高频场景两数相加、累加求和、乘法取模、坐标距离计算。我列一下我实际遇到过的溢出情况。第一类是累加。一百万个接近最大值的数据求和结果早就超了。这种时候累加变量必须声明成long并且注意中间每一步都不能用int暂存。第二类是比较器里的减法。很多人写比较器喜欢(a, b) - a - b如果 a 是正二十亿、b 是负二十亿减法结果溢出排序直接乱掉。正确写法是Integer.compare(a, b)。第三类是乘法。计算两数之积再用int接十万乘十万就是一百亿早就溢出了。这种地方要么提前转long要么用Math.multiplyExact让它在溢出时抛异常方便早期发现。int a 100_000; int b 100_000; int wrong a * b; // 溢出结果是 1410065408 long right (long) a * b; // 正确10000000000 long alsoRight Math.multiplyExact((long) a, (long) b);第四类是取模运算。题目要求结果对 1000000007 取模中间每一步乘法和加法之后都要取模不能等最后再取否则中间结果早就溢出了。2.3 浮点数比较和精度这两件事浮点数在算法里的坑比整型更隐蔽因为有时候溢出或者精度丢失不会报错只是答案偏了。我总结了两条硬规矩。不要用比较两个浮点数。0.1 0.2 0.3结果是false因为二进制表示下 0.1 和 0.2 都不是精确值。正确做法是判断差值绝对值小于一个阈值比如Math.abs(x - y) 1e-9。阈值大小取决于数据量级量级越大允许的绝对误差就应该越大或者改用相对误差判断。需要精确十进制运算时不要用double。涉及金额、需要精确到小数点后固定位数的场景用BigDecimal而且必须用字符串构造不能用double构造。new BigDecimal(0.1)会得到一个 0.1000000000000000055511151231257827 这样的值因为 0.1 这个 double 本身就不精确。double d 0.1 0.2; System.out.println(d 0.3); // false System.out.println(Math.abs(d - 0.3) 1e-9); // true BigDecimal bad new BigDecimal(0.1); // 一串尾数 BigDecimal good new BigDecimal(0.1); // 精确的 0.1 System.out.println(good.add(new BigDecimal(0.2))); // 0.32.4 值语义与引用语义那些改了却没生效的 bugJava 只有值传递这句话听起来简单但实际写算法时还是会栽。基本类型传的是值的副本方法里改了不影响外面。对象传的是引用的副本方法里通过引用改对象内容会影响外面但把参数重新指向新对象就不影响。这个特性在写递归的时候最容易出问题。你想在递归里“带回”一个结果用int参数肯定不行得用返回值或者包装类型。用int[]数组做容器是个常见技巧长度为 1 的数组当可变整数用。// 错误修改不会传出去 void dfs(int count) { count; // 递归调用... } // 正确用返回值 int dfs(int count) { return count 1; } // 也可以用单元素数组带走结果 void dfs(int[] holder) { holder[0]; }还有一种更隐蔽的情况把对象放进集合之后修改了它的字段而这个字段参与了hashCode计算。之后你再用这个对象去Map里查就查不到了因为哈希值变了落到了别的桶里。这个坑我在实际项目里遇到过排查了大半天最后发现是 key 对象被意外修改。结论是凡是用来当HashMapkey 的对象要么设计成不可变的要么确保放进去之后不再改动任何参与哈希的字段。3. 核心算法模块在 Java 里的落地写法前面铺垫了这么多语言层面的东西现在进入具体模块。我按使用频率排讲排序、二分、哈希、动态规划、并查集这几个每个都给出我实际在用的写法以及为什么这么写。3.1 排序稳定性、比较器契约和并行排序Arrays.sort有两套实现这个必须搞清楚。传基本类型数组进去走的是双轴快速排序不稳定但常数小、速度快。传对象数组进去走的是 TimSort稳定但需要额外的临时空间。所谓稳定就是相等元素的相对顺序在排序后保持不变。为什么不给基本类型用稳定排序因为对基本类型来说“相等”的两个元素本来就无法区分数值一样的两个 int 完全一样稳定性没有意义。但如果你要排的是一批记录需要保持同分数的原始顺序就必须用对象数组加 TimSort。比较器这块有个硬性契约必须满足自反性、反对称性和传递性。违反传递性会抛IllegalArgumentException: Comparison method violates its general contract!而且这个异常不一定每次都出现取决于数据排列特别难查。最常见的违反方式是这样的比较逻辑里写了a b ? 1 : -1没处理相等的情况。// 错误相等时返回 -1破坏反对称性 (a, b) - a b ? 1 : -1 // 正确处理相等 (a, b) - Integer.compare(a, b) // 多关键字排序先按第一个字段升序再按第二个字段降序 list.sort((x, y) - { int c Integer.compare(x.score, y.score); if (c ! 0) { return c; } return Integer.compare(y.age, x.age); });多关键字排序那里有个优化点。如果第一个字段的比较结果已经决定了顺序就提前返回避免无谓的第二次比较。数据量大、比较逻辑重的时候这个小优化能省不少时间。另外提一句并行排序。Arrays.parallelSort在大数组上确实更快但它用的是公共的 ForkJoin 线程池在已经有并发任务的环境里可能造成资源争抢。我一般在纯计算任务里用在服务端代码里更倾向于用普通排序避免影响其它线程。3.2 二分查找手写模板的三处细节Arrays.binarySearch有个很多人不知道的行为当数组里有重复元素时它返回的是任意一个匹配位置不保证是第一个也不保证是最后一个。如果你要找“第一个大于等于目标的位置”或者“最后一个小于等于目标的位置”必须自己写。手写二分最容易错在三处循环条件是left right还是left rightmid怎么算left和right怎么更新。我习惯用左闭右开区间[left, right)循环条件是left right这样不容易死循环。// 找第一个 target 的位置找不到返回数组长度 static int lowerBound(int[] arr, int target) { int left 0; int right arr.length; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { left mid 1; } else { right mid; } } return left; } // 找最后一个 target 的位置找不到返回 -1 static int upperBound(int[] arr, int target) { int left 0; int right arr.length; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { left mid 1; } else { right mid; } } return left - 1; }mid left (right - left) / 2这个写法是为了防止left right溢出。虽然数组长度达不到溢出量级但养成习惯没坏处万一哪天用在别的场景就救了你。二分的前提是序列有序。这个前提经常被破坏而不自知比如你在循环里对数组做了修改或者用了自定义比较器排序但二分时按自然顺序比。我建议二分之前先用小数据验证一遍或者写个断言的辅助方法在调试期检查有序性。二分的变体非常多找第一个、找最后一个、找最近的、在答案空间上二分。后一种是高级用法比如“求最小的最大值”这类问题二分的对象不是数组下标而是答案本身判断条件是“给定答案是否可行”。这类题的关键是写好单调的判定函数判定函数写对了二分模板是完全一样的。3.3 哈希表容量、树化和 key 的选择HashMap的默认初始容量是 16负载因子 0.75也就是说装到 12 个元素时扩容成 32。扩容要重新计算所有元素的哈希并搬移代价不小。如果你能预估元素数量直接指定容量能省掉多次扩容。但容量不能直接传元素个数因为HashMap内部会把容量调整到大于等于传入值的最近的 2 的幂。而且扩容阈值是容量乘负载因子所以想装 n 个元素不扩容应该传n / 0.75 1或者直接用(int) (n / 0.75f) 1。int expected 1_000_000; // 直接传 expected实际容量是 1048576阈值 786432装到 78 万就开始扩容 MapInteger, Integer m1 new HashMap(expected); // 按负载因子换算容量 2097152阈值 1572864一百万条不扩容 MapInteger, Integer m2 new HashMap((int) (expected / 0.75f) 1);这个问题在小数据量下无所谓数据量上百万时差别很明显我实测过预分配容量的版本比不预分配快一倍以上内存峰值也低。再说 key 的选择。Integer当 key 会装箱HashMapInteger, Integer每存一条要创建两个Integer对象除非命中缓存。如果 key 的范围有限比如都是 0 到 100 万之间的整数用数组直接下标访问比HashMap快一个数量级。如果 key 范围太大但实际出现的数量不多那还是得用哈希表。注意HashMap在链表长度超过 8 且总容量不小于 64 时会把链表转成红黑树查询从 O(n) 变成 O(log n)。这个转换是有条件的容量不够时优先扩容而不是树化。如果你的哈希函数分布很差大量元素撞到同一个桶性能会急剧退化。自定义对象当 key 时hashCode一定要写得分散一些。hashCode和equals的契约也必须遵守equals返回 true 的两个对象hashCode必须相等反过来不要求。只重写其中一个是很常见的错误会导致HashMap行为完全不可预期。3.4 动态规划状态定义、遍历顺序和滚动数组动态规划在 Java 里的实现难度一半在状态设计一半在内存布局。状态设计是算法层面的我重点说内存这块。最直接的做法是开一个二维数组dp[n][m]。如果 n 和 m 都到一万这就是一亿个格子int类型要占四百兆直接内存溢出。这时候要想办法降维。滚动数组是最常用的技巧。如果状态转移只依赖上一行那就只需要两行用dp[i 1][j]这样的方式交替使用。如果依赖上一行和当前行的前一个元素可以进一步压成一维但遍历方向要注意。以 0-1 背包为例一维化的写法必须倒序遍历容量维度。原因是每个物品只能用一次倒序保证你用的是上一轮的状态如果正序当前物品会被重复使用就变成了完全背包。// 0-1 背包一维滚动数组 int[] dp new int[capacity 1]; for (int i 0; i n; i) { int weight weights[i]; int value values[i]; for (int j capacity; j weight; j--) { // 倒序 dp[j] Math.max(dp[j], dp[j - weight] value); } } // 完全背包同一份代码把内层改成正序即可 for (int j weight; j capacity; j) { dp[j] Math.max(dp[j], dp[j - weight] value); }这一个正序倒序的差别我在初学者代码里见过无数次写反的。记忆方法倒序代表“回头用旧数据”正序代表“复用新数据”。另一个容易忽略的是数组填充。Java 的int数组默认初始值是 0但很多 DP 问题需要初始化为负无穷或者正无穷来表示“不可达”。Arrays.fill可以批量填但要注意Integer.MIN_VALUE参与加法会溢出得特殊处理或者用一个足够小的负数比如-0x3f3f3f3f约负十亿加几次也不会溢出到正数。3.5 并查集与图为什么数组实现比对象快并查集是图论里最常手写的结构。用对象加Map的实现方式写出来大概是这样一个MapInteger, Integer存父节点。这种写法在数据量小时没问题数据量大时慢得离谱因为每次查找都要走哈希表。标准写法是两个数组parent存父节点下标rank或size存秩。路径压缩加按秩合并之后单次操作接近常数时间。class UnionFind { private final int[] parent; private final int[] size; UnionFind(int n) { parent new int[n]; size new int[n]; for (int i 0; i n; i) { parent[i] i; size[i] 1; } } int find(int x) { // 路径压缩迭代版避免深递归 int root x; while (parent[root] ! root) { root parent[root]; } while (parent[x] ! root) { int next parent[x]; parent[x] root; x next; } return root; } boolean union(int a, int b) { int ra find(a); int rb find(b); if (ra rb) { return false; } if (size[ra] size[rb]) { int t ra; ra rb; rb t; } parent[rb] ra; size[ra] size[rb]; return true; } }find我写成迭代版而不是递归版原因是递归版在链很长的时候会栈溢出。虽然路径压缩之后链不会太长但第一次查找之前链可能已经很长了尤其是数据构造得比较极端的时候。迭代版多几行代码稳得多。邻接表也是同理。用ListListInteger存图每个节点一个ArrayList灵活性好但有大量小对象。用链式前向星head、next、to三个数组就没有对象开销遍历速度也更快。我在节点数超过十万时一律用数组版。4. 从“能跑”到“跑得快”性能调优的实操路径算法写对了只是及格能不能在约束内跑完才是关键。这一节讲几个我实际用过的调优手段都是有明确收益的不是玄学。4.1 常数因子优化三个立刻见效的改法第一个改法把循环里不变的计算提到外面。最典型的是for (int i 0; i list.size(); i)每次循环都调一次size()。虽然ArrayList的size()就是返回一个字段JIT 大概率能优化掉但换成局部变量是零成本的为什么不换。第二个改法减少方法调用层级。热循环里调用一个层层委托的方法内联可能失败。把关键逻辑内联展开哪怕代码难看一点性能收益是实打实的。第三个改法用位运算替代取模和除法。n % 2换成n 1n / 2换成n 1在 n 为非负时结果一致速度快很多。注意负数右移和除法的行为不同-3 / 2是 -1-3 1是 -2这个区别在有些场景会导致错误用之前确认取值范围。再补充一个字符串拼接。循环里用拼接字符串每次都会创建新对象。虽然 Java 9 之后编译器对简单拼接做了优化但在循环里仍然不行。正确做法是循环外用StringBuilder循环内append。StringBuilder也建议预估容量避免多次扩容。4.2 内存与 GC怎么观察怎么减少Java 算法代码跑到内存溢出通常是两个原因开了超大数组或者创建了海量短命对象。观察手段最直接的是加上 JVM 参数打印 GC 日志看垃圾回收的频率和耗时。如果发现 Young GC 特别频繁说明短命对象太多得找创建点。用采样工具抓一下热点分配位置通常很快能定位。减少对象创建有几个具体手段。第一复用数组比如多组测试数据时不要每组都新建大数组声明在循环外面清空复用。第二用原始类型数组替代集合前面说过很多次了。第三避免在循环里创建lambda捕获外部变量必要时改成静态方法或者普通循环。第四Stream的中间操作会创建大量小对象热的路径上换成普通循环。还有一个容易被忽略的递归产生的栈帧。Java 默认线程栈大小在 512KB 到 1MB 之间看平台和 JVM 版本。一个递归深度一万层的函数每层栈帧几百字节很容易就StackOverflowError。解决办法要么改成迭代要么显式指定更大的栈大小。我倾向于改迭代因为栈大小依赖运行环境换个机器可能又不够了。4.3 并行化什么时候该用什么时候是负优化parallelStream看起来很美好一行代码就能并行。但它的适用条件很苛刻数据量要足够大至少几万单个元素的计算要足够重操作要无状态且不依赖顺序还不能有共享可变状态。我实测过几个场景。对一个一百万元素的数组做简单的平方求和串行循环反而比parallelStream快因为并行拆分的开销超过了计算本身。对一个十万元素的数组做较重的加密哈希计算并行版本能快三倍左右。更可控的做法是用ForkJoinPool或者直接开线程池自己控制任务粒度和合并逻辑。但这样代码复杂度上升很多我一般只有在确认串行版本确实过不了线时才考虑。提示parallelStream用的是全局公共线程池默认并行度是 CPU 核数减一。如果你在服务端代码里用它可能跟其它任务抢线程影响整体吞吐。这种场景建议自己建一个专用线程池。5. 常见问题排查实录写了这么多年 Java 算法代码报错和诡异行为见得太多了。这一节把高频问题整理成速查表再单独讲几个我印象最深的坑。5.1 典型问题与原因速查现象最可能的原因排查方式解决方式提交超时输入解析慢 / 算法复杂度过高先注释掉算法部分只测输入换快读 / 优化复杂度答案差一点整型溢出 / 边界条件漏判用小数据对拍暴力解法转 long / 补边界内存超限开了超大二维数组 / 对象太多估算数组字节数降维 / 换数组实现排序结果乱序比较器不满足传递性换Integer.compare试修正比较器逻辑Map查不到刚放的元素key 的哈希字段被修改检查 key 是否可变用不可变 keyStackOverflowError递归太深打印递归深度改迭代 / 加栈大小并发修改异常遍历时修改集合看异常堆栈用迭代器的 remove / 收集后统一处理结果不稳定多次运行不同用了哈希顺序遍历检查是否依赖HashSet顺序换LinkedHashSet或排序这张表里我特别想强调“答案差一点”这一行。很多人遇到答案不对第一反应是算法逻辑错了改半天。实际上相当一部分是溢出或者边界漏判。排查方法很简单写一个小数据范围的暴力解法随机生成几百组小数据两个程序对拍。差异出现的那组数据手工推一遍问题立刻暴露。这个方法我用得最多比盯着代码看效率高十倍。5.2 三个我真实踩过的坑第一个坑Integer的缓存范围。早期的代码里我用比较两个Integer小数值的时候一直是对的测到某个用例突然错了。原因是Integer对 -128 到 127 之间的值有缓存这个范围内比较的是同一个对象返回 true超出范围就是两个不同对象返回 false。这个 bug 特别阴险因为它在你测试的大部分数据上都正常工作。结论包装类型一律用equals比较没有例外。第二个坑数组当HashMap的 key。我想用坐标对做 key 去重直接用了int[]数组。结果所有元素都存进去了一个都没去重。原因是数组的hashCode是身份哈希基于对象地址equals也是引用比较两个内容相同的数组是两个不同的对象。解决办法是用ListInteger当 key或者把两个坐标编码成一个long((long) x 32) | (y 0xffffffffL)后者性能好得多。第三个坑subList的视图语义。我对一个List调subList拿到子列表然后往原列表里加元素再操作子列表直接抛了并发修改异常。subList返回的不是拷贝是原列表的一个视图原列表结构变化会让视图失效。要独立使用必须先new ArrayList(list.subList(a, b))复制一份。这三个坑的共同点是都能通过编译在小数据上都能跑对只有特定条件才暴露。这也是为什么我一直强调对拍和小数据验证光靠读代码很难发现这类问题。还有一个关于递归的坑值得一提。写树的深度优先遍历时我用递归实现本地测试的树只有几百个节点一切正常。上线后遇到一条链状的极端数据深度到了几万直接栈溢出。后来改成显式栈的迭代版本才彻底解决。凡是递归深度可能跟输入规模成正比的地方都要考虑改成迭代这是我在吃过几次亏之后定下的规矩。写到这儿差不多了。我个人在实际操作中的体会是Java 算法代码的质量差异八成不在算法思想而在对这些语言细节的掌控程度。同一个思路懂装箱和扩容代价的人写出来和不懂的人写出来跑起来就是两个东西。上面这些模板和数字都是我一遍遍调出来的你可以直接拿去用但更重要的是理解每个选择背后的代价——知道自己在付什么账才知道什么时候该换一种付法。
