Hi 大家好，我是张小猪。欢迎来到『宝宝也能看懂』系列之 leetcode 周赛题解。
这里是第 175 期的第 1 题，也是题目列表中的第 1346 题 -- 『检查整数及其两倍数是否存在』
给你一个整数数组 arr，请你检查是否存在两个整数 N 和 M，满足 N 是 M 的两倍（即，N = 2 * M）。
更正式地，检查是否存在两个下标 i 和 j 满足：
i != j0 <= i, j < arr.lengtharr[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
EASY
题目的描述比较正式，如果简单的说其实就是，给定了一个数组，需要确认其中是否有一个数是另一个数的两倍。
相信一直看小猪题解的小伙伴们读完这道题就会有思路啦，毕竟也是 EASY 难度，小猪也就不做过多的分析啦。唯一需要提到的一点就是，我们是需要寻找到另一个数而不是当前数，即如果数组中只存在一个 0，那么是不能返回 true 的。并且，如果 x 是 y 的两倍，那么 y 必然是 x 的一半。这句话看起来是废话，不过它背后的意思是，我们在遍历的过程中，只需要进行单方向的检查即可，不用对左右两个方向都检查了。
下面给出两种常见方案：
- 暴力搜索，针对每个数字在数组中去寻找目标数字。
- 存储历史数值，以供后续数字直接查找到。
暴力搜索没有过多可以说的内容，只需要注意到上面分析中提到的两个问题即可。具体流程如下：
- 遍历数组。
- 对于每一个值，遍历它后面的值，看看是否存在它的一半或者两倍。
- 返回结果。
基于这个流程，我们可以实现类似下面的代码：
const checkIfExist = arr => {
for (let i = 0; i < arr.length; ++i) {
for (let j = i + 1; j < arr.length; ++j) {
if (arr[j] === arr[i] << 1 || arr[j] === arr[i] / 2) return true;
}
}
return false;
};对于存储历史值的方案，我们需要用到额外的空间来记录。这里我们可以用定长数组，也可以用集合。具体流程如下：
- 遍历数组。
- 记录出现过的值。
- 判断出现过的值是否有当前值的一半或者两倍。
- 返回结果。
基于这个流程，小猪这里把两种储存方式的代码都写了出来，供小伙伴们参考：
// 基于定长 Uint8Array 记录
const checkIfExist = arr => {
const neg = new Uint8Array(1000);
const pos = new Uint8Array(1000);
for (const val of arr) {
const arr = val > 0 ? pos : neg;
const v2 = Math.abs(val);
if (arr[v2 << 1] === 1 || arr[v2 / 2]) return true;
arr[v2] = 1;
}
return false;
};// 基于 Set 记录
const checkIfExist = arr => {
const set = new Set();
for (const val of arr) {
if (set.has(val << 1) || set.has(val / 2)) return true;
set.add(val);
}
return false;
};周赛第一题惯例送分。其实这个问题在比较初级的面试中小猪也用过，其中直接的暴力搜索方案是很容易被面试者提到，可是能提到 O(n) 的优化方案却不到一半。
小猪也不清楚具体的原因，所以这里专门把两种方案都写了出来。希望能帮到还不太清楚的小伙伴，小猪爱你们哟~
