從LeetCode學演算法 - 89 Hash Table (9)

1346. Check If N and Its Double Exist (Easy)

Question

Given an array arr of integers, check if there exist two integers N and M such that N is the double of M ( i.e. N = 2 * M).

More formally check if there exist two indices i and j such that :

i != j
0 <= i, j < arr.length
arr[i] == 2 * arr[j]

Example 1

1
2
3
Input: arr = [10,2,5,3]
Output: true
Explanation: N = 10 is the double of M = 5,that is, 10 = 2 * 5.

Example 2

1
2
3
Input: arr = [7,1,14,11]
Output: true
Explanation: N = 14 is the double of M = 7,that is, 14 = 2 * 7.

Example 3

1
2
3
Input: arr = [3,1,7,11]
Output: false
Explanation: In this case does not exist N and M, such that N = 2 * M.

Constraints

2 <= arr.length <= 500
-10^3 <= arr[i] <= 10^3

分析/解題

給定一組整數陣列，檢查當中是否存在兩個數N, M使得N = 2 * M。
(留意不可使用重複的index)

乍看之下有沒有覺得一陣熟悉？
沒錯，LeetCode最開始的第一題0001.Two Sum 的套路，
跟這個非常的相似，只不過從兩數相加等於固定數，
變成一個是另一個的兩倍。另一方面，我們只要將存在與否輸出，
所以不用記錄是什麼配對 。

那麼，按照先前的做法，我們需要做的事情是：

檢查現在的值有沒有符合之前的配對 ，若有，就直接回傳True即可。
(先前使用HashMap/Dictionary，這次可以使用HashSet/Set)
將當前的值對應到的配對 擺進Set當中，
由於當前的值x對應到之後的y有可能是 x = 2 * y 或 y = 2 * x，
所以我們要一次將兩種可能都放進去。
這樣子整個Set的總大小會變成2N，但不會影響檢查速度。
(因為HashSet/Set同樣是使用hash function的機制)
全部檢查完，仍然沒有符合的狀況，則回傳False。

依此，寫成程式碼如下：

Java

Java的部分，由於限制資料型態，
要留意處理除以2的部分，不能讓它自動做整數除法，
所以先檢查能否被2整除，可以的狀況才將其加入Set中 。
(使用HashSet ，檢查是否存在值使用contains() ，add() 來加入元素)

Python

Python的部分，由於/2直接會變成float，沒有特別被限制，
我們可以直接選擇加入而略過檢查的部分。
(反正小數點也不會被對到嘛XD)
(使用set() 開一個Set，in / not in 來檢查，並用update 來加入多個元素)
(先處理存在或先處理不存在的狀況都可以，看自己的喜好)

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(N)，記得乘以2倍空間上是常數，不要講O(2N)歐XD)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

感謝大家對這系列文章的支持！這邊跟大家自我工商一下：

筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
Medium優惠(最後一波早鳥優惠了，不確定調回原價是什麼時候)： ** https://hiskio.com/courses/319?promo_code=VE9Q5VE**