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

题目描述

给你一个整数数组 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

解法

方法一：哈希表

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

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

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

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

Python3JavaC++GoTypeScript

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

class Solution {
    public boolean checkIfExist(int[] arr) {
        Set<Integer> s = new HashSet<>();
        for (int x : arr) {
            if (s.contains(x * 2) || ((x % 2 == 0 && s.contains(x / 2)))) {
                return true;
            }
            s.add(x);
        }
        return false;
    }
}

class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        unordered_set<int> s;
        for (int x : arr) {
            if (s.contains(x * 2) || (x % 2 == 0 && s.contains(x / 2))) {
                return true;
            }
            s.insert(x);
        }
        return false;
    }
};

func checkIfExist(arr []int) bool {
    s := map[int]bool{}
    for _, x := range arr {
        if s[x*2] || (x%2 == 0 && s[x/2]) {
            return true
        }
        s[x] = true
    }
    return false
}

function checkIfExist(arr: number[]): boolean {
    const s: Set<number> = new Set();
    for (const x of arr) {
        if (s.has(x * 2) || (x % 2 === 0 && s.has((x / 2) | 0))) {
            return true;
        }
        s.add(x);
    }
    return false;
}

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

题目描述

解法

方法一：哈希表

评论