检查 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 及其双精度数是否存在

<?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 关联数组来存储迄今为止遇到的元素。
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中文网其他相关文章！