LeetCode 1346题解析：检查数组中是否存在两倍数元素

1. 问题分析与解法思路

今天我们来聊聊LeetCode第1346题"检查整数及其两倍数是否存在"。这道题看似简单，但实际处理起来有不少细节需要注意。题目要求我们判断数组中是否存在两个元素，其中一个元素是另一个元素的两倍。

1.1 问题重述

给定一个整数数组arr，检查是否存在两个下标i和j满足：

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

1.2 解题思路分析

这道题最直观的解法是暴力枚举，时间复杂度O(n²)。但我们可以通过排序和二分查找优化到O(nlogn)。具体思路如下：

1. 首先对数组进行去重处理（但保留0，因为0的两倍还是0）
2. 对数组进行排序
3. 对于每个元素，计算其两倍值（正数）或半值（负数）
4. 在剩余元素中使用二分查找判断是否存在该值

注意：处理负数时需要特别注意，因为负数的两倍会变得更小，而我们需要找的是其半值（即除以2）。

2. 代码实现详解

让我们仔细分析这个100%击败率的解法代码：

2.1 去重处理

vector<int> tmp{arr[0]}; for(int i = 1; i < n; i++) { if(arr[i] != arr[i-1] || arr[i]==0) tmp.push_back(arr[i]); } arr = std::move(tmp);

这里有几个关键点：

1. 保留第一个元素作为初始值
2. 只有当当前元素与前一个不同，或者当前元素是0时才保留
3. 使用std::move避免不必要的拷贝

技巧：对于0的特殊处理是因为0的两倍还是0，如果数组中有两个0，就应该返回true。

2.2 排序数组

sort(arr.begin(), arr.end());

排序是为了后续可以使用二分查找，将时间复杂度从O(n²)降低到O(nlogn)。

2.3 查找两倍数

for(int i = 0; i < n-1; i++) { t = (arr[i] < 0)? arr[i]/2 : arr[i] * 2; acc = (arr[i] < 0)? arr[i]/2.0 : arr[i] * 2.0; ind = lower_bound(arr.begin() + i + 1, arr.end(), t) - arr.begin(); if(ind != n && (float)arr[ind] == acc) { return true; } }

这部分是核心逻辑：

1. 对于正数，我们找它的两倍（*2）
2. 对于负数，我们找它的一半（/2）
3. 使用lower_bound进行二分查找
4. 比较时使用浮点数，避免整数除法的问题

3. 关键细节解析

3.1 负数处理的艺术

负数处理是这道题最容易出错的地方。例如：

• 对于-4，我们需要找-2（而不是-8）
• 对于-5，我们需要找-2.5，但数组中只有整数，所以实际上找不到

代码中巧妙地同时计算了整数和浮点数版本：

t = (arr[i] < 0)? arr[i]/2 : arr[i] * 2; // 整数版本，用于lower_bound acc = (arr[i] < 0)? arr[i]/2.0 : arr[i] * 2.0; // 浮点版本，用于精确比较

3.2 浮点数比较的必要性

使用浮点数比较是为了避免整数除法的问题。例如：

• 5/2在整数运算中是2，但实际我们需要的是2.5
• 通过比较(float)arr[ind] == acc可以精确判断

3.3 lower_bound的使用技巧

ind = lower_bound(arr.begin() + i + 1, arr.end(), t) - arr.begin();

这里有几个要点：

1. 只在i+1到结尾的范围内查找，避免重复检查
2. lower_bound返回的是第一个不小于t的元素位置
3. 需要检查ind是否在有效范围内

4. 复杂度分析与优化空间

4.1 时间复杂度分析

1. 去重操作：O(n)
2. 排序操作：O(nlogn)
3. 外层循环：O(n)
4. 内层二分查找：O(logn) 总体时间复杂度：O(nlogn)

4.2 空间复杂度分析

使用了额外的tmp数组，空间复杂度O(n)

4.3 可能的优化方向

1. 使用哈希表可以达到O(n)时间复杂度，但空间复杂度也是O(n)
2. 可以尝试在排序后的数组中使用双指针法

5. 边界条件与测试案例

5.1 必须考虑的边界情况

1. 空数组
2. 单元素数组
3. 全零数组
4. 正负数混合数组
5. 有重复元素的数组

5.2 典型测试案例

// 案例1：正数情况 [10,2,5,3] → true (5*2=10) // 案例2：负数情况 [-10,5,-2,3] → true (-10/2=-5) // 案例3：零的情况 [0,0] → true (0*2=0) // 案例4：无解情况 [1,3,5,7] → false

6. 常见错误与调试技巧

6.1 常见错误类型

1. 忘记处理负数情况，直接用*2
2. 整数除法导致精度丢失
3. 重复元素处理不当
4. 数组越界访问

6.2 调试技巧

1. 打印中间变量值，特别是t和acc
2. 检查lower_bound的返回位置
3. 验证去重后的数组是否正确
4. 使用小规模测试案例逐步验证

7. 扩展思考与类似题目

7.1 类似题目推荐

1. Two Sum (LeetCode 1)
2. 3Sum (LeetCode 15)
3. Contains Duplicate (LeetCode 217)

7.2 算法思想延伸

这道题体现了几个重要的算法思想：

1. 排序预处理优化查找
2. 二分查找的应用
3. 边界条件的全面考虑
4. 浮点数比较的特殊处理

在实际工程中，这种先预处理数据再高效查询的思路非常常见，比如数据库索引就是类似的思想。