1346。檢查 N 及其雙精度數(shù)是否存在

難度：簡單

主題：數(shù)組、哈希表、兩個指針、二分查找、排序

給定一個整數(shù)數(shù)組 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 循環(huán)，在 hashTable 中維護(hù) [0, i - 1] 中的數(shù)組元素。
2. 在循環(huán)的每一步中檢查到目前為止我們是否已經(jīng)看到元素 2 * arr[i]。
3. 還要檢查我們是否看到了 arr[i] / 2，以防 arr[i] % 2 == 0。

解決方案：

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

這是一個分步解決方案：

計劃：

1. 迭代數(shù)組。
2. 對于每個元素 arr[i]，檢查我們是否在哈希表中見過 2 * arr[i] 或 arr[i] / 2 （如果 arr[i] 是偶數(shù)）。
3. 如果滿足任何條件，則返回 true。
4. 否則，將 arr[i] 添加到哈希表并繼續(xù)下一個元素。
5. 如果最后沒有找到匹配項，則返回 false。

讓我們用 PHP 實現(xiàn)這個解決方案：1346。檢查 N 及其雙精度數(shù)是否存在

<?php
/**
 * @param Integer[] $arr
 * @return Boolean
 */
function checkIfExist($arr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$arr1 = [10, 2, 5, 3];
$arr2 = [3, 1, 7, 11];

echo checkIfExist($arr1) ? 'true' : 'false'; // Output: true
echo "\n";
echo checkIfExist($arr2) ? 'true' : 'false'; // Output: false
?>

解釋：

1. 哈希表：我們使用 $hashTable 關(guān)聯(lián)數(shù)組來存儲迄今為止遇到的元素。
2. 第一個條件：對于每個元素arr[i]，我們檢查哈希表中是否存在arr[i] * 2。
3. 第二個條件：如果元素是偶數(shù)，我們檢查哈希表中是否存在 arr[i] / 2。
4. 添加到哈希表：檢查后，我們將arr[i]添加到哈希表中以供將來參考。
5. 返回：如果我們找到匹配項，我們立即返回true。如果循環(huán)后沒有找到匹配項，我們返回 false。

時間復(fù)雜度：

• 時間復(fù)雜度為O(n)，其中n是數(shù)組的長度。這是因為每個元素都被處理一次，并且在哈希表中檢查或添加元素平均需要恒定的時間。

空間復(fù)雜度：

• 由于哈希表需要存儲，空間復(fù)雜度為O(n)。

聯(lián)系鏈接

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

如果您想要更多類似的有用內(nèi)容，請隨時關(guān)注我：

• 領(lǐng)英
• GitHub

以上是檢查 N 及其雙精度數(shù)是否存在的詳細(xì)內(nèi)容。更多信息請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！