What is the best pattern for Check If N and Its Double Exist?

The best pattern is a single pass with a hash set of previously seen numbers. For each value x, check whether 2 * x is already seen or whether x is even and x / 2 is already seen.

Why is the hash set solution better than sorting here?

Sorting can work, but it adds extra work to a problem that only asks whether any valid pair exists. The hash set scan matches the condition directly and finishes in linear time on average.

Why do we check before inserting the current number?

That preserves the requirement that the two values come from different indices. It also avoids incorrect self-matching when the current value could satisfy the relation with itself, especially for 0.

Do we really need to check x / 2 as well as 2 * x?

Yes, because the array order is arbitrary. In arr = [10,2,5,3], the larger value 10 appears before 5, so checking only doubles would miss the valid pair.

How should I think about the zero case in this problem?

Zero only forms a valid answer when there are at least two zeroes at different indices. The check-before-insert order handles this cleanly because the second zero will find the first one already in the set.

#1346

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

检查整数及其两倍数是否存在

给你一个整数数组 arr ，请你检查是否存在两个整数 N 和 M ，满足 N 是 M 的两倍（即， N = 2 * M ）。更正式地，检查是否存在两个下标 i 和 j 满足： i != j 0 arr[i] == 2 * arr[j] 示例 1：输入： arr = [10,2,5,3] 输出： …

数组哈希表双指针二分查找排序

题目描述

给你一个整数数组 arr，请你检查是否存在两个整数 N 和 M，满足 N 是 M 的两倍（即，N = 2 * M）。

更正式地，检查是否存在两个下标 i 和 j 满足：

i != j
0 <= i, j < arr.length
arr[i] == 2 * arr[j]

示例 1：

输入：arr = [10,2,5,3]
输出：true
解释：N = 10 是 M = 5 的两倍，即 10 = 2 * 5 。

示例 2：

输入：arr = [7,1,14,11]
输出：true
解释：N = 14 是 M = 7 的两倍，即 14 = 2 * 7 。

示例 3：

输入：arr = [3,1,7,11]
输出：false
解释：在该情况下不存在 N 和 M 满足 N = 2 * M 。

提示：

2 <= arr.length <= 500
-10^3 <= arr[i] <= 10^3

lightbulb

解题思路

方法一：哈希表

我们定义一个哈希表 $s$ ，用于记录访问过的元素。

遍历数组 $arr$ ，对于每个元素 $x$ ，如果 $x$ 的两倍或者 $x$ 的一半在哈希表 $s$ 中，那么返回 true。否则将 $x$ 加入哈希表 $s$ 。

若遍历结束后没有找到满足条件的元素，返回 false。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $arr$ 的长度。

1

2

3

4

5

6

7

8

9

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

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
They mention storing values from indices [0, i - 1] while scanning, which points directly to a seen-set solution.
question_mark
They ask how to avoid comparing every pair, which usually means replace brute force with O(1) membership checks.
question_mark
They emphasize different indices i and j, which is a clue to check before inserting the current value into the hash set.

warning

常见陷阱

外企场景

error
Checking only one direction, such as whether 2 * x was seen, misses pairs where the larger number appears earlier.
error
Forgetting the even-number guard before checking x / 2 can create incorrect matches for odd values.
error
Adding the current number to the set before lookup can falsely treat one element as both sides of the pair, especially around 0.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Sort the array and use binary search for each value, but the logic becomes less direct than the hash lookup pattern.
arrow_right_alt
Use a frequency map if you also want to reason explicitly about duplicates like two zeroes.
arrow_right_alt
Return the actual index pair instead of a boolean, which requires storing positions rather than only seen values.

help

常见问题

外企场景

继续练习

#1782 统计点对的数目 #532 数组中的 k-diff 数对 #350 两个数组的交集 II