1346. 检查整数及其两倍数是否存在
1346. 检查整数及其两倍数是否存在
🟢 🔖 数组
哈希表
双指针
二分查找
排序
🔗 力扣
LeetCode
题目
Given an array arr
of integers, check if there exist two indices i
and j
such that :
i != j
0 <= i, j < arr.length
arr[i] == 2 * arr[j]
Example 1:
Input: arr = [10,2,5,3]
Output: true
Explanation: For i = 0 and j = 2, arr[i] == 10 == 2 _ 5 == 2 _ arr[j]
Example 2:
Input: arr = [3,1,7,11]
Output: false
Explanation: There is no i and j that satisfy the conditions.
Constraints:
2 <= arr.length <= 500
-10^3 <= arr[i] <= 10^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
解题思路
这道题可以使用哈希集合 (Set) 解决。
- 遍历数组中的每个数字
num
。 - 对于每个
num
,检查以下两种情况:- 是否存在
2 * num
在集合中(即num
的两倍已出现)。 - 是否存在
num / 2
在集合中(即num
是某个数的两倍)。
- 是否存在
- 如果满足上述任意条件,则返回
true
。 - 否则,将当前数字添加到集合中。
复杂度分析
- 时间复杂度:
O(n)
,其中n
是数组长度,需要遍历数组中的每个元素一次,每次查找和插入集合的复杂度为O(1)
,总时间复杂度为O(n)
, - 空间复杂度:
O(n)
,使用一个集合来存储最多n
个元素。
代码
/**
* @param {number[]} arr
* @return {boolean}
*/
var checkIfExist = function (arr) {
let set = new Set();
for (let num of arr) {
// 检查 set 中是否存在 2 * num or num / 2
if (set.has(2 * num) || set.has(num / 2)) {
return true;
}
// 将当前数字加入 set 中
set.add(num);
}
// 没找到两倍数
return false;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
2154 | 将找到的值乘以 2 | [✓] | 数组 哈希表 排序 1+ | 🟢 | 🀄️ 🔗 |