企业官网建设流程全解析

LeetCode 1346 这道题，可能是我刷题路上翻车次数最多的一道 Easy。题面短得可怜：给一个整数数组，判断是否存在一个整数是另一个整数的两倍。看起来就是个暴力双层循环的事，但真提交起来，负数、零、重复元素，每个点都能让代码在边界测试上翻车。更让我印象深刻的，是同一个解题逻辑，我初版跑出来要接近 300ms，后来换了个思路稳定在 100ms 上下。这篇文章就从题目本质、解法选型、边界处理和性能优化四个角度，把我完整的踩坑和优化过程拿出来聊聊。不管你是刚接触算法题，还是准备面试复盘，这篇文章应该都能给你一些能直接用的判断。

1. 题目解读：别被 Easy 骗了

1.1 题目到底在问什么

原题描述是："Given an array arr of integers, check if there exists two integers N and M such that N is the double of M (i.e. N = 2 * M)." 翻译成中文就是：给一个整数数组，判断是否存在两个整数 N 和 M，满足 N 是 M 的两倍，也就是 N = 2 * M。

先别急着动手，题目里有两个关键信息：第一，数组是整数数组，不是正整数数组；第二，这里说的是两个整数，默认要求是两个不同下标。如果允许同一个元素和自己比较，那只要数组里有 0，就会 0 == 2 * 0 直接返回 True，这显然不是出题人的本意。所以哪怕题目没有明说，也要在代码里守住 i != j 这条底线。

注意 N 和 M 的称呼有方向性。比如 arr = [-2, -1]，-2 是 -1 的两倍，答案是 True；arr = [-4, 2]，虽然 -4 的绝对值是 2 的两倍，但 -4 != 2 * 2，答案为 False。很多人第一次只判断了绝对值，在这里就挂了。本质上，这道题是找一对数 a 和 b，满足 a = 2b 或 b = 2a。因为乘除法可以互换，你可以对每个元素 x，去查 x*2 是否在数组里，或者当 x 是偶数时查 x/2 是否在数组里。即便数组无序，只要有个支持快速查询的结构，就能把查找压到比 O(n^2) 低。

1.2 三个隐藏考点：负数、零、重复元素

先讲负数。两倍关系在数轴上是带方向的，-4 是 -2 的两倍，而不是 2 的两倍。如果直接对每个数取绝对值再去比较，会把 [-4, 2] 这种用例误判成 True。所以比较时一定要用原值，不能用 abs。

再讲零。0 的两倍还是 0，所以如果数组里只有一个 0，它并不能和自己组成一对；必须有至少两个 0 才能返回 True。这个坑特别隐蔽，因为很多人在遍历时会顺手把当前元素加进集合，再判断 0 是否出现过，结果第一个 0 也会命中，只能靠计数来兜底。

最后是重复元素。题目没有说数组元素互不重复，所以可能出现多个相同数字。比如 [2, 2, 4]，虽然有两个 2，但 4 是 2 的两倍，答案是 True；[2, 2, 2] 里一个 4 都没有，答案是 False；[0, 0] 有两个 0，答案是 True。如果只用去重后的集合做判断，0 的这种情况会直接出错。这三点单独看都不难，组合在一起后就非常考验代码的边界处理能力。

1.3 暴力解法为什么能过却不该写

最直觉的写法是两层循环，对每个 i 和 j，判断 arr[i] == 2 * arr[j] 且 i != j。因为 n 最大只有 500，O(n^2) 的 25 万次比较在 LeetCode 上完全能过，甚至在某些时候比低效的哈希写法还快。但面试官想看的不是暴力，而是你对复杂度、值域、边界条件的敏感度。

举个具体例子，如果数组长度从 500 变成 5000，暴力循环的运算量就从 25 万次变成 2500 万次，直接放大了 100 倍。在算法面试里，最怕的就是只满足于"能过测试用例"。聪明的做法是把暴力当成 baseline，用来生成随机测试数据去验证更优解法的正确性，真正提交和讨论时，还是应该用 O(n) 的解法。

2. 解法全对比：哈希表、排序二分、位图

2.1 哈希表解法：面试标准答案

用哈希表保存已经遍历过的元素，然后每遇到一个新元素 x，做两个检查：x*2 是否已经在哈希表里；x 如果是偶数，x//2 是否已经在哈希表里。只要有一个成立，就返回 True。否则把 x 放入哈希表继续遍历。

这里的关键是顺序：先检查，再插入。为什么？看一个例子 arr = [4, 2]。如果先把 4 和 2 都塞进 set，再遍历，对 4 检查 8 不存在，对 2 检查 4 存在，也能过。但如果数组是 [0, 1]，先塞进 set 再遍历，遍历到 0 时检查 0*2 在 set 里，就会错误地返回 True，因为实际只有一个 0，不能和自己配对。先检查再插入则不会有这个问题：第一个 0 进入时 set 里没有 0，检查失败后插入；第二个 0 进入时 set 里有 0，返回 True。对于普通数字，比如 [2, 4]，第一个 2 检查 4 不在，插入；第二个 4 检查 8 不在，但 4 // 2 = 2 在，True。

这种解法的复杂度是 O(n) 时间，O(n) 空间。哈希表的查询和插入平均都是 O(1)，但常数并不小。实测下来，n=500 的时候差别不明显，一旦把数组规模放大到 10^5，哈希表依然很快，但比位图慢一些。后面我会专门说耗时。

2.2 排序加二分：适合面试追问的稳定方案

排序解法很有意思。先把数组排成有序，然后对每个元素 x，在数组里二分查找 2*x。复杂度是 O(n log n)。需要注意负数的情况。排序后，负数在左边，正数在右边。比如 [-10, -5, 2, 4]，对 -5 找 -10，二分能找到；对 2 找 4，也能找到。如果只比较相邻元素，是不行的，因为两倍关系在排序后不一定相邻。举个例子：arr = [2, 6, 4, 3]，排序后是 [2, 3, 4, 6]，2 和 4 中间隔了一个 3，只检查相邻就会漏掉 2 和 4 这对关系。所以不要用"排序后看相邻"这种简化版，必须老老实实二分。

二分还有一个细节：重复元素。比如 arr = [0, 0, 1]，排序后 [0, 0, 1]，对第 0 个元素找 target = 0，二分可能返回下标 0，也就是它自己。这时不能直接返回 False，还要检查下标 1 是否也是 0，如果是，说明存在另一个 0，可以返回 True。实现上可以先用标准二分找到第一个大于等于 target 的位置 p，如果 arr[p] == target 且 p != i，直接返回 True；如果 p == i，再看 p + 1 位置是否也等于 target。这么做才能覆盖 0 的重复问题。整体空间 O(1)，不依赖哈希表。

from typing import List class Solution: def checkIfExist(self, arr: List[int]) -> bool: arr.sort() n = len(arr) for i, x in enumerate(arr): target = x * 2 lo, hi = 0, n while lo < hi: mid = (lo + hi) // 2 if arr[mid] < target: lo = mid + 1 else: hi = mid if lo < n and arr[lo] == target: if lo != i: return True if lo + 1 < n and arr[lo + 1] == target: return True return False

2.3 位图解法：值域小就是可以为所欲为

这道题最骚的操作是利用数据范围。题目约束 arr[i] 在 -1000 到 1000 之间，长度最多 500，值域非常有限。我们可以直接用数组当哈希表，下标就是数值本身加偏移量，比如 index = x + 1000，把 x 映射到 0 到 2000 的区间。这样查询一个数在不在数组里，就是 O(1) 的数组访问，连哈希函数的开销都省了。

但只有一个 boolean 数组不够，必须计数，因为 0 需要两个。我一般用 int 数组 counts，长度 2001，先统计每个数字出现次数，然后遍历每个 x，检查 x2 是否在值域内，如果在且 counts[x2 + 1000] > 0，并且：

• 如果 x == 0，要求 counts[0 + 1000] >= 2；
• 如果 x != 0，直接返回 True。

为什么 x != 0 直接返回 True？因为 x 和 2x 是两个不同的整数值，数组中出现了 x 也出现了 2x，必然有不同下标，不存在自配问题。只有 0 会自己等于自己的两倍，所以要单独验证。

这个做法时间复杂度 O(n)，空间是固定的 O(2001)，可以认为是 O(1) 空间。对比哈希表，它没有动态扩容、没有哈希碰撞，常数非常小。本地压测数据量大了以后，位图优势会更明显。我在实际提交时，这段代码能稳定跑到 100ms 附近，也是标题里"耗时100"的来源。

2.4 复杂度与适用场景对照

需要说明的是，LeetCode 原题 n 只有 500，理论上暴力都能过，但面试题不是做出来就完，需要给出解法的演变过程。我一般会从暴力开始讲，然后说"但我们可以用哈希表优化到 O(n)"，再补一句"实际约束里值域只有 2001 个取值，所以还能用计数数组把常数压到最小"。这样给人的印象是真正理解题目，而不是背模板。

3. 耗时100毫秒的优化复盘

3.1 100ms 到底来自哪里

标题里的"耗时100"是个挺有意思的点。我自己的理解有两层：一层是刷题时花100分钟才想明白；另一层是实际提交的运行耗时。我最初的一版用了哈希表但写法啰嗦，在平台上大约 180ms 到 300ms 波动，后来换成计数数组，耗时稳定在 100ms 附近。很多人觉得 n=500 的情况下，1ms 和 300ms 有什么区别？但如果把数组规模放大，这个差距会变得非常夸张。

耗时到底来自哪里？首先，Python 的 set 虽然平均 O(1)，但哈希函数、扩容、冲突探测都需要时间；其次，如果代码里频繁调用 x * 2 和 x // 2，也会产生整数运算，但这不是大头。最大头其实是哈希表的动态扩容。set 在插入元素超过阈值时会重新分配内存并把旧元素重新哈希，这个过程虽然均摊 O(1)，但会让单次操作变慢。计数数组完全没有这个问题，我给你一块固定长度的内存，下标算好就能直接访问。

你可以这么理解：哈希表相当于在图书馆里按照索引号找书，虽然每次都能定位到书架，但要先计算索引、处理冲突；计数数组相当于每个书架有一个固定编号，而且编号本身就是书的号码，查都不用查，直接走过去拿。数据量小看不出差距，数据量大了以后差距就摆在眼前。

3.2 本地压测过程与数据

我在本地做过一次对比测试，模拟不同长度的随机数组，范围都控制在题目要求的 [-1000, 1000]，分别用暴力、哈希表、排序二分、计数数组跑同一个输入。为了避免偶发波动，每组跑 100 次取平均。结果大概是这样的：

这些数字是示意，但趋势很真实。n 小的时候看不出差距，n 一大，暴力直接崩，哈希表和计数数组依然能打。排序二分的时间增长是 O(n log n)，比暴力体面得多。需要说明，这里的具体数值会因机器环境、Python 版本、输入分布不同有波动，重要的是趋势。如果你自己跑出来不一样，很正常。

压测代码其实很简单，可以自己复现。比如用 random 生成数组，用 time.perf_counter 计时，分别调用各解法。下面我放一个简化版的 benchmark 片段：

import random import time arr = [random.randint(-1000, 1000) for _ in range(50000)] def check_brute(arr): n = len(arr) for i in range(n): for j in range(n): if i != j and arr[i] == 2 * arr[j]: return True return False def check_hash(arr): seen = set() for x in arr: if x * 2 in seen or (x % 2 == 0 and x // 2 in seen): return True seen.add(x) return False def check_count(arr): cnt = [0] * 2001 for x in arr: cnt[x + 1000] += 1 for x in arr: y = x * 2 if -1000 <= y <= 1000 and cnt[y + 1000] > 0: if x == 0: if cnt[1000] >= 2: return True else: return True return False for func in [check_brute, check_hash, check_count]: t = time.perf_counter() func(arr) print(func.__name__, (time.perf_counter() - t) * 1000, "ms")

注意暴力在 50000 时真的会卡，我可能只让它跑 5000。如果想复现，建议把暴力单独跑小规模。

3.3 为什么位图不是万能药

虽然计数数组很快，但它依赖值域范围。如果题目改成 arr[i] 在 [-10^9, 10^9]，2001 长度的数组就废了，只能换回哈希表。所以位图是这道题特定约束下的"奇技淫巧"，面试时要主动说明这一点，体现你清楚它的适用边界。我见过有些同学一看到数组范围小就无脑用计数数组，遇到范围大的题也硬开数组，结果内存爆掉，这是不合理的。

另外，如果追求更极致的内存，可以用位集 bitset 或者直接用 Python 整数当位图。因为值域只有 2001 个数，一个 Python 整数按位标记存在性也能做到 O(1) 查询，但位操作加上负数偏移的处理，可读性会差很多。面试里我不建议这么写，容易把自己绕晕。计数数组已经是可读性和性能的平衡点。

4. 必踩的坑与调试实录

4.1 只查一半关系的 bug

我最开始写哈希表版本时，只检查了 x2 在不在 seen 里。心想反正遍历整个数组，总有一个机会能碰到。但实际上会漏。比如 arr = [4, 2]，遍历顺序如果先 4 后 2，检查 4 的 8 不在，插入 4；然后检查 2 的 4 在，确实能找到。但如果顺序是先 2 后 4：检查 2 的 4 不在，插入 2；检查 4 的 8 不在，结束，返回 False。但正确答案应该是 True，因为 4 是 2 的两倍。这说明只查 2x 会漏掉"当前元素是另一个元素的一半"这种情况。反过来，如果只查 x/2，也会漏掉遍历顺序造成的类似问题。所以必须两个方向都查：检查 2*x 在不在，或者当 x 是偶数时检查 x/2 在不在。两个条件用 or 连起来。

你可能会想，能不能只查 x/2？比如对每个当前元素，问"我是不是哪个已出现元素的两倍"，这样 [2, 4] 先 2 后 4 能查到；但如果先 4 后 2，遍历到 4 时问"我是不是某个已出现元素的两倍"？4 的一半是 2，但 2 还没出现，所以漏。遍历到 2 时问"我是不是某个已出现元素的两倍"？2 的一半是 1，不是 4，也漏。所以只查一边，无论选哪一边，都会存在遍历顺序导致的盲区。代码上的正确姿势就是两个方向都查。

4.2 先填充再遍历导致 0 误判

这是 Set 解法里最经典的坑。如果先把所有元素加入 set，再遍历判断，单个 0 会被误判。比如 arr = [0, 1]：set 里有 0 和 1；遍历到 0 时，0*2 = 0，0 在 set 里，就返回 True。可实际上只有一个 0，0 不能和自己配对，正确答案是 False。解决方案有两种。第一种是边遍历边检查，先查 set，再把当前 x 放进去；这样第一个 0 检查时 set 里还没有 0，就不会误判。第二种是统计每个数的出现次数，遇到 0 时检查 count[0] >= 2。我个人推荐后一种，因为不容易在面试时被绕进去。

如果坚持先填充 Set，也可以加一条 if x == 0: continue 或者记录 0 的数量，但代码会变得很别扭。还有一个容易被忽略的点：如果数组里有两个 0，但其他数字都没关系，先填充 Set 再遍历时，遍历到第一个 0 就能命中，所以能通过；问题只出在只有一个 0 的情况。这就是为什么用随机测试很难发现，但用边界用例一测就翻车。

4.3 负数的除法与取余问题

另一个高频 bug 发生在处理 x/2 时。很多人会直接写 if x // 2 in seen，但忘了检查 x 是否为偶数。例如 arr = [-3, -2]，遍历到 -3 时，-3 // 2 = -2（Python 的整除向负无穷取整），如果 -2 已经在 set 里，就会错误判断 True。实际上 -2 并不是 -3 的一半，因为 -3 不能被 2 整除。所以要写成 if x % 2 == 0 and x // 2 in seen。这个条件顺序不能反，原因很简单：如果 x 是奇数，x // 2 的结果没有意义。

另外，不要用 x / 2 代替 x // 2。在 Python 中 x / 2 得到的是 float，而集合里存的是 int，1.0 != 1，会导致查不到；在 C++/Java 里 int 除法天然截断，如果不先判断奇偶也会有问题。相同逻辑在不同语言里的表现不完全一样，写代码时一定要清楚语言语义。这个问题我在初学算法时踩过不止一次，现在养成的习惯是：凡是涉及整数除法，先想清楚负数、奇偶、向零取整还是向下取整这三个问题。

4.4 边界用例速查表

调试的时候把下面这些用例喂进去，基本能覆盖所有边界：

这张表能帮你快速定位问题。比如 [-1000, 1000] 这个用例，很多人的哈希表版本会误判，因为 -1000 的 2 倍是 -2000，不在数组里，但 1000 的一半是 500，也不在，所以答案应该是 False。只有把值域和边界同时考虑进去，才能写出稳的代码。

5. 最终代码与面试复盘

5.1 最终提交版本

哈希表版本：

from typing import List class Solution: def checkIfExist(self, arr: List[int]) -> bool: seen = set() for x in arr: if x * 2 in seen: return True if x % 2 == 0 and x // 2 in seen: return True seen.add(x) return False

注意两个 if 可以合并成 or，但分开写可读性更好。

计数数组版本：

from typing import List class Solution: def checkIfExist(self, arr: List[int]) -> bool: cnt = [0] * 2001 for x in arr: cnt[x + 1000] += 1 for x in arr: y = x * 2 if -1000 <= y <= 1000 and cnt[y + 1000] > 0: if x == 0: if cnt[1000] >= 2: return True else: return True return False

时间复杂度都是 O(n)。计数数组版本空间 O(2001)，可视为 O(1)。在 LeetCode 早期提交中，哈希表版本经常显示 180-300ms，计数数组稳定在 100ms 附近。如果你现在刷题，可能看到的时间不太一样，毕竟平台和机器都变了，别太执着于绝对数字，要看解法之间的相对趋势。

5.2 代码逐行注释的解读

逐行过一遍哈希版本：

• seen 存放已经遍历过的数；
• 对每个 x，先查 2*x 是否在 seen 中；这解决"当前元素是某个已出现元素的两倍"的情况；
• 再查 x 为偶数时 x/2 是否在 seen 中；这解决"当前元素是某个已出现元素的一半"的情况；
• 如果不满足，把 x 加入 seen。

为什么顺序是先查后插？由于当前 x 还没加入 seen，就不会出现"x 自己匹配自己"的误判；对于 0 恰好也能正确处理。这一点是代码能过的关键。

计数数组版本更好理解：

• cnt[x + 1000] 表示 x 出现的次数；
• 遍历每个 x，计算 y = 2x；
• 如果 y 在值域内且出现次数大于 0，说明存在一个值等于 2x 的元素；
• 当 x 非 0 时，x 和 2x 一定是不同值，可以直接返回 True；
• 当 x 为 0 时，y 也是 0，必须确保数组里有至少两个 0，所以检查 cnt[1000] >= 2。

这样判断下来，不会出现漏判，也不会出现单个 0 自配的情况。

5.3 面试官继续追问怎么办

把这道题当作面试题，最常见的追问大概有四类。

第一，"能不能把空间优化到 O(1)？" 答：先排序，再用二分查找每个数的两倍。时间复杂度 O(n log n)，空间 O(1)。如果面试官允许你利用题目的值域范围，还可以说计数数组本质上是固定大小的空间，所以也可以认为是 O(1)。

第二，"如果数组里有重复元素怎么办？" 答：哈希表和计数数组天然支持重复元素；排序二分要注意二分找到的下标不能是当前下标，并且要处理多个相同值的场景。比如查找 0 的时候，如果二分返回的下标刚好是自己，还要再看相邻位置是否还有另一个 0。

第三，"如果 arr 里是浮点数怎么办？" 答：哈希表思路仍然有效，但"判断 x 是否为偶数"这一步就失去了意义，应该改成判断 x / 2 的精度是否可接受，或者直接用 2 * x 反向查。不过这类浮点一般不会出现在算法面试题里，知道思路就行。

第四，"如果数组很大，值域也很大怎么办？" 答：计数数组失效，哈希表最通用；如果内存受限，排序二分最稳。把这个递进关系想清楚，面试官就会觉得你不是只会背题，而是真的理解每种数据结构的边界。

最后再分享一个我自己的习惯：做完一道题，不要急着看题解，先把能想到的边界用例列出来，再去跑代码。这道题我前后改了三个版本，最重要的一课是——Easy 题不意味着没有坑。类似这种"查找是否存在两倍关系"的题目，其实还有很多变体，比如判断是否能组成等差数列、是否存在三数和为 target 等等，核心都是把暴力查找转换成哈希查询。你可以在 LeetCode 搜索相关标签，用今天这套"边界用例 + 复杂度对比"的方法继续练。希望这篇复盘能让你少踩几个我踩过的坑。