【Leetcode Python题解】「1346. Check If N and Its Double Exist」

题目：1346. Check If N and Its Double Exist

题目描述

给定一个整数数组 arr，检查是否存在两个不同的索引 i 和 j，满足：

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

示例

示例 1:

1
2
3
输入：arr = [10,2,5,3]
输出：true
解释：对于 i = 0 和 j = 2，arr[i] = 10 等于 2 * 5 = 2 * arr[j]

示例 2:

1
2
3
输入：arr = [3,1,7,11]
输出：false
解释：不存在满足条件的 i 和 j。

约束条件

  • 2 <= arr.length <= 500
  • -10³ <= arr[i] <= 10³

解题思路

这道题可以用多种方法解决，我们来分析两种主要的解法：暴力解法和哈希表解法。

1. 暴力解法

最直观的解法是使用两层循环，遍历所有可能的数对。

1
2
3
4
5
6
7
def checkIfExist(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n):
            if i != j and arr[i] == 2 * arr[j]:
                return True
    return False

复杂度分析：

  • 时间复杂度：O(n²)，其中 n 是数组长度
  • 空间复杂度：O(1)，只使用了常数额外空间

2. 哈希表解法

使用哈希表可以显著优化时间复杂度。我们只需要一次遍历数组，同时用哈希表记录已经遇到的数字。

1
2
3
4
5
6
7
def checkIfExist(arr):
    seen = set()
    for num in arr:
        if num * 2 in seen or (num % 2 == 0 and num // 2 in seen):
            return True
        seen.add(num)
    return False

复杂度分析：

  • 时间复杂度：O(n)，只需要遍历一次数组
  • 空间复杂度：O(n)，需要额外的哈希表空间

代码优化案例

让我们看一个初始版本的代码，以及如何优化它：

原始版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        hashmap = {}
        for i, item in enumerate(arr):
            hashmap[i] = item
            if item * 2 in hashmap.values():
                j = next(k for k, v in hashmap.items() if v == item * 2)
                if i != j:
                    return True
            if item//2 in hashmap.values() and item%2==0:
                j = next(k for k, v in hashmap.items() if v == item//2)
                if i != j:
                    return True
        return False

优化版本：

1
2
3
4
5
6
7
8
class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        seen = set()
        for num in arr:
            if num * 2 in seen or (num % 2 == 0 and num // 2 in seen):
                return True
            seen.add(num)
        return False

优化要点

  1. 数据结构选择

    • 使用集合(set)替代字典(dict)
    • 不需要存储索引信息，只关注值的存在性

  2. 代码简化

    • 合并重复的检查逻辑
    • 移除不必要的变量和计算
    • 使用更简洁的条件判断

  3. 性能提升

    • 避免使用 hashmap.values() 遍历
    • 使用集合的 O(1) 查找特性
    • 减少重复计算

关键注意点

  1. 边界情况处理

    • 考虑数组中有 0 的情况（0 的两倍仍然是 0）
    • 注意负数的处理
    • 确保不使用同一个索引（i != j）

  2. 数值检查

    • 需要同时检查一个数的两倍和一半
    • 检查一半时要确保数字是偶数

  3. 性能优化

    • 使用恰当的数据结构（集合）
    • 避免不必要的计算和遍历

总结

这道题展示了如何通过选择适当的数据结构和优化代码逻辑来提升算法的性能。从初始的暴力解法到使用哈希表，再到代码的优化，每一步都带来了显著的改进。最终的解决方案不仅运行效率高，而且代码简洁易懂。

关键是要理解：

  1. 暴力解法虽然直观，但效率低下
  2. 哈希表提供了最优的时空权衡
  3. 代码优化不仅是为了效率，也是为了可读性和可维护性