LeetCode 题解工作台
数组中最长的方波
给你一个整数数组 nums 。如果 nums 的子序列满足下述条件，则认为该子序列是一个 方波 ： 子序列的长度至少为 2 ，并且 将子序列从小到大排序 之后 ，除第一个元素外，每个元素都是前一个元素的 平方 。 返回 nums 中 最长方波 的长度，如果不存在 方波 则返回 -1 。 子序列 也是…
5
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们先用哈希表记录数组中的所有元素，然后枚举数组中的每个元素作为子序列的第一个元素，将该元素不断平方，并判断平方后的结果是否在哈希表中，如果在，则将平方后的结果作为下一个元素，继续判断，直到平方后的结果不在哈希表中，此时判断子序列的长度是否大于 ，如果是，则更新答案。 时间复杂度 $O(n \times \log \log M)$，空间复杂度 。其中 为数组 的长度，而 为数组 中的元素的…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 nums 。如果 nums 的子序列满足下述条件，则认为该子序列是一个 方波 ：
- 子序列的长度至少为
2，并且 - 将子序列从小到大排序 之后 ，除第一个元素外，每个元素都是前一个元素的 平方 。
返回 nums 中 最长方波 的长度，如果不存在 方波 则返回 -1 。
子序列 也是一个数组，可以由另一个数组删除一些或不删除元素且不改变剩余元素的顺序得到。
示例 1 ：
输入：nums = [4,3,6,16,8,2] 输出：3 解释：选出子序列 [4,16,2] 。排序后，得到 [2,4,16] 。 - 4 = 2 * 2. - 16 = 4 * 4. 因此，[4,16,2] 是一个方波. 可以证明长度为 4 的子序列都不是方波。
示例 2 ：
输入：nums = [2,3,5,6,7] 输出：-1 解释：nums 不存在方波，所以返回 -1 。
提示：
2 <= nums.length <= 1052 <= nums[i] <= 105
解题思路
方法一：哈希表 + 枚举
我们先用哈希表记录数组中的所有元素，然后枚举数组中的每个元素作为子序列的第一个元素，将该元素不断平方，并判断平方后的结果是否在哈希表中，如果在，则将平方后的结果作为下一个元素，继续判断，直到平方后的结果不在哈希表中，此时判断子序列的长度是否大于 ，如果是，则更新答案。
时间复杂度 ，空间复杂度 。其中 为数组 的长度，而 为数组 中的元素的最大值。
class Solution:
def longestSquareStreak(self, nums: List[int]) -> int:
s = set(nums)
ans = -1
for x in nums:
t = 0
while x in s:
x *= x
t += 1
if t > 1:
ans = max(ans, t)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n \cdot \log n) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
The candidate should show a clear understanding of the array scanning technique and how hash lookups can optimize the search for subsequences.
- question_mark
An efficient implementation using hash tables or dynamic programming will demonstrate good problem-solving and optimization skills.
- question_mark
Candidates may struggle with the correct approach to binary search optimization, which can lead to an O(n^2) solution if not handled properly.
常见陷阱
外企场景- error
Forgetting to sort the array first, which can make it impossible to find valid subsequences.
- error
Not using hash lookups effectively, which can lead to excessive computation time when searching for square relationships.
- error
Confusing the problem with simple subsequence length problems, leading to incorrect solutions.
进阶变体
外企场景- arrow_right_alt
Consider variations where the subsequence length could be constrained differently.
- arrow_right_alt
What if the subsequence has to be contiguous? That would require additional modifications.
- arrow_right_alt
Handle arrays with duplicate elements and ensure they don’t interfere with subsequence counting.