1346. Check If N and Its Double Exist
Problem
Given an array arr of integers, check if there exist two indices i and j such that :
i != j0 <= i, j < arr.lengtharr[i] == 2 * arr[j]
https://leetcode.com/problems/check-if-n-and-its-double-exist/
Example 1:
Input:
arr = [10,2,5,3]
Output:true
Explanation: Fori = 0andj = 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³ <= arr[i] <= 10³
Test Cases
class Solution:
def checkIfExist(self, arr: List[int]) -> bool:solution_test.py下载完整源码
import pytest
from solution import Solution
from solution2 import Solution as Solution2
@pytest.mark.parametrize('arr, expected', [
([10,2,5,3], True),
([3,1,7,11], False),
([-2,0,10,-19,4,6,-8], False),
([0,0], True),
])
class Test:
def test_solution(self, arr, expected):
sol = Solution()
assert sol.checkIfExist(arr) == expected
def test_solution2(self, arr, expected):
sol = Solution2()
assert sol.checkIfExist(arr) == expected
Thoughts
把所有数字放进集合,然后遍历所有的偶数,如果它的一半在集合中,则结果为真。
但是 0 比较特殊,0 除以二或者乘以二都还是 0,但去分不出来是不是同一个数组下标的 0。
可以在创建集合的时候,顺便检查数组中 0 的个数,如果超过一个则结果为真。
也可以一遍创建集合一边创建集合一遍就进行检查。但为了没有遗漏,就要同时检查下一个数的一半(限偶数)和两倍是否在集合中。这样能够自适应 0。
Code
solution.py下载完整源码
class Solution:
def checkIfExist(self, arr: list[int]) -> bool:
store: set[int] = set()
for n in arr:
if n == 0 and n in store:
return True
store.add(n)
return any(n != 0 and n & 1 == 0 and (n >> 1) in store for n in arr)
solution2.py下载完整源码
class Solution:
def checkIfExist(self, arr: list[int]) -> bool:
store: set[int] = set()
for n in arr:
if (n & 1 == 0 and (n >> 1) in store) or (n << 1) in store:
return True
store.add(n)
return False
评论需要 JavaScript。