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 != j
0 <= i, j < arr.length
arr[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: For i = 0 and j = 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

1 2	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

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。