这篇文章的创作目的是科普一下力扣的运行时间，进而识别出一些无意义的追求beats 100%的情况。能做到beats 100%固然是好事，但也要量力而行，并避免无意义的劳动。

运行时间

首先介绍一下力扣上代码的运行时间是怎么算出来的。通过测试可以发现，提交后显示的代码执行用时是所有数据用时之和。(不知道的同学麻烦点个赞谢谢)。另外测试数据不是一成不变的，大家可以通过LC网站内部或者LeetCode-Feedback的反馈增加数据叉掉错误/会超时的代码，一些周赛时通过的错误代码可能一段时间后就过不了了。但是增加数据后不一定会立即重测以前的所有代码，所以先提交的同学可能会有优势。如果发现重新交一遍运行时间柱状图上排名第一的代码并不能AC或者很慢，很可能就是这个原因。特别地，周赛刚比完后可能在评论区看到大量号称双百的代码，实际上是因为其他人的提交还没有显示在运行时间图上，所以你就是第一。
注：在特殊情况下也可能减少数据，比如官方发现标程或者评论区高票会挂掉的时候，可能会缩小数据范围并重造数据。

有一个小细节是数据的读入时间。以C++为例，大家会发现有的题目加上ios::sync_with_stdio(0)会变快，特别是输入数据比较大的时候，这是因为力扣的C++计时方式会算上读入数据的时间。(有兴趣的同学甚至可以看到数据在后台是怎么被输入输出的。对某些数据格式，比如vector<vector<>>的读入简直慢到令人发指。) Java就没有这个问题，所以一些输入规模大，算法复杂度低的题Java可以暴打C++，例如C++优化到死92ms，Java 9ms，还有同学吵起来了(就不at当事人了)。所以跨语言比较运行时间没有太大意义，运行时间图也是每种语言独立的。其他语言的情况我了解不多，欢迎在评论区补充。

另外一点是评测机的配置问题。比如CN站和US站使用的是不同的CPU，同一份代码的运行时间会存在区别，甚至可能一边超时一边不超时。更离谱的是US站居然有三种评测机配置，有Intel(R) Xeon(R) Platinum 8275CL CPU @ 3.00GHz，Intel(R) Xeon(R) Platinum 8168 CPU @ 2.70GHz和Intel(R) Xeon(R) Gold 6140 CPU @ 2.30GHz，这三种配置用的还是同一个运行时间图，有时候重交一遍运气好甚至能快一倍。所以想刷个速度首先还得烧香求自己被分到最好的那个评测机...
更新：过了几周发现评测机cpu配置变成六种了，又多了Intel(R) Xeon(R) Platinum 8124M CPU @ 3.00GHz，Intel(R) Xeon(R) CPU E5-2697A v4 @ 2.60GHz和Intel(R) Xeon(R) CPU E5-2650 v4 @ 2.20GHz。不确定是不是使用了云端服务导致cpu一直在变。
(话说今天看了下CN站其实也有两种CPU，都是Intel(R) Xeon(R) Platinum 8369B CPU但一个是2.70GHz，一个是2.90GHz。跑起来好像没有肉眼可见的区别，这是标错了么？)
(2024.2 更新：美服 cpu 反超国服了，现在美服是 AMD EPYC 7B13，国服没变。有的代码现在只有美服能过了。)

时间限制

不同题目可能会有不同的时间限制，并且同一题不同语言的时间限制也可能不同。python跑得慢，时限就会放宽一点，比如C++ 2 秒 python 10 秒，导致有的题python反而比C++有优势，Python，Java 和 JS 暴力都能过，C++ 同样的写法就是过不了。当然也有C++占优势的时候。不过如果是写正解的话一般官方会让各种语言都可以AC的。

因为运行时间是各数据上的总时间之和，所以可能发生奇怪的情况，如下图：

这个的完整触发条件我也不是非常清楚，赞同评论区的推测，可能是跑完了所有数据，但恰好在最后一个数据上总时间超时了。

因为提交的时候不知道总数据组数，所以大家只能估计一下来判断会不会超时。一般为了覆盖到各种边界情况，测试数据大概有100组左右，但是极限数据会很少，比如3~5组，如果只有一组的话数据就比较水了。C++的话一般一秒时限总共不超过1e8次操作会比较稳，有自信的同学也可以用1e9。

一个冷知识：如果数据范围设计不合理的话，力扣后台的标程也是可能超时的，导致没有标准输出。比如这样：

beats 100%

1. 一些无意义的情况

大家提交一下自己的代码发现能beats 100%当然会很开心，不过了解了运行时间的知识之后，我们就可以识别出一些刷beats 100%的无意义的情况。例如：

1. 比赛后一天内刷出的beats 100%。原因见上，点柱状图看一下会发现可能只有三五个人在跟你竞争，其他人的数据还没更新呢。
2. 大量反复提交。计时结果总会有几ms到十几ms的一点小波动，所以连交个两三次倒也无可厚非(我也这样干)，毕竟和你的新算法比较的可能是几百个写同一种算法的人，你交个几遍也还是公平的。但是如果和别人拿着一样的代码，靠着交的多就拿了第一，那也没什么意思。(不过对个人来说这种情况其实发生的可能性是比较小的，因为其他人的总提交数太多了，可能刷个成百上千次才能靠随机的计时抖动把所有人比下去。) 因为计时波动问题，如果前几名的运行时间差距不大的话，柱状图上最快的那个代码不一定就是真正最快的，可能只是运气最好的。另外总运行时间越短这种运气成分占比会越大。
3. 读入优化。如果只靠加读入优化把其他没加的都比下去，那就没什么意思。不过跑得快的其他人都加了的话那你想刷100%也只能加了。考虑到读入时间，对于C++来说，如果一个O(n)复杂度的题，输入格式是vector<vector>，那运行时间基本毫无意义了，全靠谁运气好在后台读入数据的时候快一点。可能读入就占了100ms，你的算法只跑了4ms。
4. 特判掉最大的那组数据，这个是真的无聊...

有一个特殊情形是针对数据设计算法。这也是一种能力，我也见过 $O(n^4)$ 实际跑得比 $O(n^3)$ 还快的题(然后还卡不掉，只是最坏数据上很慢而已)，但这个时候主要还是得让太弱的官方数据背锅。如果目标是学习更好的算法的话，还是尽量去写最坏复杂度比较好的算法吧。

2. 一些技巧

这里也分享一些beats 100%的技巧。使用更好的算法当然是最本质的，对于一些通用的常数优化技巧我也不再赘述，不过此外还有一些力扣平台特有的技巧。注意到绝大部分题的测试数据都是由大量小数据+少量大数据组成，然后力扣的测试方式是对于每组数据new一个Solution class出来跑(对于C++来说)，所以可以让所有instance共享同一个全局变量数组，这样会更快(不过要注意跑完每组后清零)。比如这个例子中只对运行当前数据后改变的数组位置清零，会比memset整个大数组或者新开数组更快。在同一个例子中，对于vector& num令int *a = &num[0]的效果是用指针访问vector内的元素(强调一下，这样是不好的，平时写代码不要学)，虽然力扣的clang开了O2，但似乎效果不太好，vector仍然非常慢。在这个题解里我也展示过了这个小技巧的威力，让暴力算法得以AC。

对于Python来说的话，numpy是一个很有效的加速手段，甚至可以帮助python对其他语言形成优势(比如有的题python比C++多开了5倍时限，普通写法会慢个十倍，就吃亏了；但换成numpy的操作之后只慢了两三倍，就赚了，导致其他语言的暴力过不了，只有python能过)。可以看这个，这个或者这个例子。

在算法方面，因为力扣的数据范围可能比较小，所以复杂度更优的算法不一定在实践中跑得更快，我也碰到过更好的算法刷不到rank 1的例子。然后如果你觉得自己的算法很好，也应该很快，但怎么都刷不到第一，建议把当前最快的那个算法重交一遍试试，大概率是加了数据但还没重测过，甚至最快的那个是个错的。另外官方会过一段时间重测一遍，可能过几个月你beats 100%的代码就从柱状图上自动消失了，所以beats 100%不一定代表你打败了历史上的所有提交。

顺便也说一下内存的问题。leetcode统计内存消耗的时候只会计入被访问过的内存块，所以即使我们开了一个$5\cdot 10^8$那么大的int数组(理论值为约2000MB)，如果只使用其中的少量元素的话也不会超出内存限制。那么在一些情况下可以直接拿数组当哈希表用，让代码跑得更快。例子

最后分享一个冷知识：跑到严格rank 1的当天你是不会显示在柱状图上的，比如这样。如果比之前的第一名快非常多的话甚至连"You are here!"那个灰条都会消失不见~

注：文章里的图可能被吃掉了。估计过个一两天会显示出来。