LEETCODE 1346. Check If N and Its Double Exist 解题思路分析

题目大意：

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

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1346

解题思路分析：

这道题难度不大，解题思路与Two Sum非常类似，Two Sum是求是否存在两个数的和是target，而本题是求是否存在两数之商为2。

我们遍历一遍数组，将每个数字存在Set集合中，如果Set中存在该数字的倍数，返回true。另外，如果set中存在该数字一半的数字，也可以返回true。这里注意一下，由于都是正数操作，计算当前数字一半（除以2）的时候，要先看当前数字是否能被2整除。

实现代码：

public boolean checkIfExist(int[] arr) {
    // 记录出现过的数字
    Set<Integer> set = new HashSet<>();
    // 遍历数组中每一个数字
    for(Integer n : arr){
        // 如果当前数字可以被2整除，并且set中存在当前数一半的数字，返回true
        if(n%2==0 && set.contains(n/2)) return true;
        // 如果set中存在当前数的倍数，返回true
        if(set.contains(n*2)) return true;
        // 将当前数加入set
        set.add(n);
    }
    return false;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 99.41% of Java online submissions for Check If N and Its Double Exist.

Memory Usage: 39.3 MB, less than 100.00% of Java online submissions for Check If N and Its Double Exist.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1346-check-if-n-and-its-double-exist-解题思路分析/