Easy

题目描述

给你一个整数数组 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 和 N 的两倍数。

提示：

  • 2 <= arr.length <= 500
  • -1000 <= arr[i] <= 1000

解题思路

解题思路

这是一个典型的查找问题，需要检查数组中是否存在某个数是另一个数的两倍。我们可以采用多种解法：

方法一：哈希表（推荐）

遍历数组时，对于每个元素 arr[i]，检查：

  1. 是否已经见过 2 * arr[i]（当前元素的两倍）
  2. 是否已经见过 arr[i] / 2（当前元素的一半，仅当 arr[i] 是偶数时）

使用哈希表存储已经访问过的元素，实现 O(1) 时间复杂度的查找。

方法二：暴力解法

使用两层循环，对于每个元素检查数组中是否存在它的两倍或一半。时间复杂度较高但思路简单。

方法三：排序 + 二分查找

先排序数组，然后对每个元素使用二分查找寻找其两倍数。

特殊情况处理

需要特别注意 0 的情况：如果数组中有两个 0，那么一个 0 是另一个 0 的两倍，应该返回 true。

哈希表解法是最优选择，时间复杂度 O(n)，空间复杂度 O(n)，代码简洁易懂。

代码实现

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

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

public class Solution {
    public bool CheckIfExist(int[] arr) {
        HashSet<int> seen = new HashSet<int>();
        
        foreach (int num in arr) {
            if (seen.Contains(2 * num) || (num % 2 == 0 && seen.Contains(num / 2))) {
                return true;
            }
            seen.Add(num);
        }
        
        return false;
    }
}

var checkIfExist = function(arr) {
    const seen = new Set();
    
    for (let num of arr) {
        if (seen.has(num * 2) || seen.has(num / 2)) {
            return true;
        }
        seen.add(num);
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型哈希表解法暴力解法排序+二分查找
时间复杂度O(n)O(n²)O(n log n)
空间复杂度O(n)O(1)O(1)

推荐解法：哈希表解法，时间效率最优，代码简洁。

相关题目