Leetcode 1346:检查整数及其两倍数是否存在(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1346:检查整数及其两倍数是否存在(超详细的解法!!!)

in leetcode with 0 comment

给你一个整数数组 arr,请你检查是否存在两个整数 NM,满足 NM 的两倍(即,N = 2 * M)。

更正式地,检查是否存在两个下标 ij 满足:

示例 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 。

提示:

解题思路

首先不难想到暴力解法,也就是通过两层循环遍历数组,然后进行判断即可。

class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        for i, l in enumerate(arr):
            for j, r in enumerate(arr):
                if i != j and (l == 2 * r or r == 2 * l):
                    return True
        return False

更优秀的解法就是参看Leetcode 1:两数之和思路,遍历arr的过程中记录哪些数访问过(通过Hash map),然后判断当前元素的两倍或者一半之前有没有出现过即可。

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

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses