檢查 N 及其雙精度數是否存在

1346。檢查 N 及其雙精度數是否存在

難度：簡單

主題：陣列、雜湊表、兩個指標、二分查找、排序

給定一個整數數組 arr，檢查是否存在兩個索引 i 和 j 使得：

• i != j
• 0
• arr[i] == 2 * arr[j]

範例1：

• 輸入： arr = [10,2,5,3]
• 輸出： true
• 解釋： 對於 i = 0 且 j = 2，arr[i] == 10 == 2 * 5 == 2 * arr[j]

範例2：

• 輸入： arr = [3,1,7,11]
• 輸出： false
• 解釋：不存在滿足條件的 i 和 j。

約束：

• 2
• -10³ 3

提示：

1. 從 i = 0 到 arr.length 循環，在 hashTable 中維護 [0, i - 1] 中的陣列元素。
2. 在循環的每一步中檢查到目前為止我們是否已經看到元素 2 * arr[i]。
3. 也要檢查我們是否看到了 arr[i] / 2，以防 arr[i] % 2 == 0。

解：

我們可以使用哈希表（關聯數組）來追蹤在迭代數組時已經遇到的元素。這個想法是檢查每個元素 arr[i] 是否已遇到其雙倍（即 2 * arr[i]）或一半（即 arr[i] / 2 如果它是偶數）。

這是一個逐步解決方案：

計劃：

1. 迭代數組。
2. 對於每個元素 arr[i]，檢查我們是否在哈希表中見過 2 * arr[i] 或 arr[i] / 2 （如果 arr[i] 是偶數）。
3. 如果滿足任何條件，則傳回 true。
4. 否則，將 arr[i] 加入哈希表並繼續下一個元素。
5. 如果最後沒有找到符合項，則傳回 false。

讓我們用 PHP 實作這個解：1346。檢查 N 及其雙精確度數是否存在

解釋：

1. 雜湊表：我們使用 $hashTable 關聯數組來儲存迄今為止遇到的元素。
2. 第一個條件：對於每個元素arr[i]，我們檢查哈希表中是否存在arr[i] * 2。
3. 第二個條件：如果元素是偶數，我們檢查雜湊表中是否存在 arr[i] / 2。
4. 加入到雜湊表：檢查後，我們將arr[i]加入哈希表以供將來參考。
5. 回傳：如果我們找到匹配項，我們立即回傳true。如果循環後沒有找到匹配項，我們回傳 false。

時間複雜度：

• 時間複雜度為O(n)，其中n是陣列的長度。這是因為每個元素都被處理一次，並且在雜湊表中檢查或添加元素平均需要恆定的時間。

空間複雜度：

• 由於雜湊表需要存儲，空間複雜度為O(n)。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是檢查 N 及其雙精度數是否存在的詳細內容。更多資訊請關注PHP中文網其他相關文章！