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.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
本文链接: https://leetcode.jp/leetcode-1346-check-if-n-and-its-double-exist-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。