LeetCode 解題練習：Check If N and Its Double Exist

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/check-if-n-and-its-double-exist/

中文描述

給定一個整數陣列 arr，找出陣列中兩個不一樣位置的元素是不是符合 arr[i] * 2 = arr[j]，其中 i != j。 

範例一：

輸入 arr = [-1, 8, 2, 1, 4]

輸出 true

因為元素 4 是元素 2 * 2。

範例一：

輸入 arr = [-1, 8, 3, 1, 4]

輸出 false

因為沒有任一兩個元素符合 arr[i] * 2 = arr[j]，其中 i != j。

解法一：

先排序，在用二分搜尋法找有沒有目前陣列元素兩倍的數字出現在不同的索引位置。

Python Code

class Solution:

    def checkIfExist(self, arr: List[int]) -> bool:

        arr.sort()

        count = len(arr)

        for i in range(count):

            pro = arr[i] * 2

            left = 0

            right = len(arr) - 1

            while left <= right:

                middle = (left + right) // 2

                if arr[middle] == pro and i != middle:

                    return True

                elif arr[middle] > pro:

                    right = middle - 1

                else:

                    left = middle + 1

           

        return False

解法二：

使用 hastTable 來儲存陣列的每一個元素 ele，在每次加入一個元素時檢查 ele * 2 與 ele / 2 是否有在 hashTable 出現過，若有，回傳 true。在加完陣列的每一個元素之後，回傳 false。

Python Code

class Solution:

    def checkIfExist(self, arr: List[int]) -> bool:

        hashTable = {}

        for ele in arr:

            if ele * 2 in hashTable or ele / 2 in hashTable:

                return True

            hashTable[ele] = 0

       

        return False