LeetCode 题解工作台
二倍数对数组
给定一个长度为偶数的整数数组 arr ，只有对 arr 进行重组后可以满足 “对于每个 0 ，都有 arr[2 * i + 1] = 2 * arr[2 * i] ” 时，返回 true ；否则，返回 false 。 示例 1： 输入： arr = [3,1,3,6] 输出： false 示例 2：…
4
题型
4
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
class Solution: def canReorderDoubled(self, arr: List[int]) -> bool:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i + 1] = 2 * arr[2 * i]” 时，返回 true；否则，返回 false。
示例 1：
输入：arr = [3,1,3,6] 输出：false
示例 2：
输入：arr = [2,1,2,6] 输出：false
示例 3：
输入：arr = [4,-2,2,-4] 输出：true 解释：可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]
提示：
0 <= arr.length <= 3 * 104arr.length是偶数-105 <= arr[i] <= 105
解题思路
方法一：哈希表 + 排序
class Solution:
def canReorderDoubled(self, arr: List[int]) -> bool:
freq = Counter(arr)
if freq[0] & 1:
return False
for x in sorted(freq, key=abs):
if freq[x << 1] < freq[x]:
return False
freq[x << 1] -= freq[x]
return True
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N \log N) |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Can the candidate efficiently solve the problem with an optimal time complexity?
- question_mark
Does the candidate understand the importance of sorting and hash lookups for this problem?
- question_mark
Is the candidate able to handle both positive and negative numbers correctly in the array?
常见陷阱
外企场景- error
Forgetting to handle negative numbers, which can cause incorrect results when pairing elements.
- error
Not efficiently updating the frequencies of elements after pairing, leading to incorrect answers.
- error
Trying to brute force the problem without using sorting or a hash map for efficient lookups.
进阶变体
外企场景- arrow_right_alt
Allowing odd-length arrays as input and adjusting the logic to handle such cases.
- arrow_right_alt
Extending the problem to handle arrays with more complex relationships between elements.
- arrow_right_alt
Optimizing the solution to handle very large arrays with constraints closer to `arr.length <= 10^5`.