题目描述

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

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

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

样例

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

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

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

限制

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

算法

(集合) $O(n)$

1. 将每个非零数字放入集合，同时统计 0 出现的次数。
2. 枚举每个数字，判断它的二倍是否存在于集合中，如果存在，则返回 true。
3. 最后，如果 0 出现的次数大于等于 2 次，也返回 true。
4. 不满足条件 2 和 3，返回 false。

时间复杂度

• 集合插入和查询的时间复杂度为常数，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存放集合。

C++ 代码

class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        unordered_set<int> h;
        int zeros = 0;
        for (int x : arr)
            if (x != 0)
                h.insert(x);
            else
                zeros++;

        for (int x : arr)
            if (h.find(2 * x) != h.end())
                return true;

        return zeros >= 2;
    }
};