2501-数组中最长的方波

给你一个整数数组 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 <= 105
• 2 <= nums[i] <= 105

视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场周赛的看法~

---

方法一：暴力枚举

由于数组元素至少为 2，平方 k 次后，元素至少为 2^{2^{k-1}。

因此只要暴力枚举初始项，不断平方即可，至多循环 \log\log U 次，这里 U=max(\textit{nums})。

检查元素是否在数组中，可以用哈希表预处理。

[sol1-Python3]

class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        ans, s = 0, set(nums)
        for x in s:
            cnt = 0
            while x in s:
                cnt += 1
                x *= x
            ans = max(ans, cnt)
        return ans if ans > 1 else -1

[sol1-Go]

func longestSquareStreak(nums []int) (ans int) {
	set := map[int]bool{}
	for _, x := range nums {
		set[x] = true
	}
	for x := range set {
		cnt := 1
		for x *= x; set[x]; x *= x {
			cnt++
		}
		ans = max(ans, cnt)
	}
	if ans == 1 {
		return -1
	}
	return
}

func max(a, b int) int { if b > a { return b }; return a }

复杂度分析

• 时间复杂度：O(n\log\log U)，其中 n 为 nums 的长度，U=max(\textit{nums})。
• 空间复杂度：O(n)。

方法二：记忆化搜索

[sol2-Python3]

class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        s = set(nums)
        @cache
        def dfs(x: int) -> int:
            if x not in s: return 0
            return 1 + dfs(x * x)
        ans = max(map(dfs, s))
        return ans if ans > 1 else -1

[sol2-Go]

func longestSquareStreak(nums []int) (ans int) {
	set := map[int]bool{}
	for _, x := range nums {
		set[x] = true
	}
	dp := map[int]int{}
	var f func(int) int
	f = func(x int) int {
		if !set[x] {
			return 0
		}
		if v, ok := dp[x]; ok {
			return v
		}
		dp[x] = 1 + f(x*x)
		return dp[x]
	}
	for x := range set {
		ans = max(ans, f(x))
	}
	if ans == 1 {
		return -1
	}
	return
}

func max(a, b int) int { if b > a { return b }; return a }

复杂度分析

• 时间复杂度：O(n)，其中 n 为 nums 的长度。至多有 O(n) 个状态。
• 空间复杂度：O(n)。