2501. 数组中最长的方波

🟠   🔖  数组 哈希表 二分查找 动态规划 排序  🔗 力扣 LeetCode

题目

You are given an integer array nums. A subsequence of nums is called a square streak if:

• The length of the subsequence is at least 2, and
• after sorting the subsequence, each element (except the first element) is the square of the previous number.

Return the length of thelongest square streak in nums , or return -1 if there is no square streak.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: nums = [4,3,6,16,8,2]

Output: 3

Explanation: Choose the subsequence [4,16,2]. After sorting it, it becomes [2,4,16].

• 4 = 2 * 2.
• 16 = 4 * 4.

Therefore, [4,16,2] is a square streak.

It can be shown that every subsequence of length 4 is not a square streak.

Example 2:

Input: nums = [2,3,5,6,7]

Output: -1

Explanation: There is no square streak in nums so return -1.

Constraints:

• 2 <= nums.length <= 10^5
• 2 <= nums[i] <= 10^5

题目大意

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

解题思路

要解决这个问题，可以利用集合来快速查找平方数，同时通过对输入数组进行排序来方便构造平方序列。

1. 将数组中的每个元素存入一个集合中，以便快速查找平方值。

2. 对输入数组 nums 进行去重和排序，以便后续构建平方序列时，能够保证元素的顺序。

3. 构建平方序列：

   • 遍历已排序的数组，针对每个元素 num，检查是否可以形成平方序列：
     • 如果 num 是 1，跳过，因为 1 的平方是 1，不会形成有效的平方序列。
     • 从当前元素开始，尝试查找下一个平方数，即 num * num。
     • 如果找到了，就将平方序列长度加一，并从集合中删除当前平方数，防止重复计算，并更新当前元素为下一个平方数。
     • 重复这一过程直到找不到下一个平方数为止，并记录当前的平方序列长度。

4. 在每次构建平方序列时，检查长度是否大于当前记录的最长平方序列长度，并进行更新。

5. 如果找到的最长平方序列长度大于等于 2，则返回该长度；否则返回 -1。

复杂度分析

• 时间复杂度：O(n log n)，其中 n 是数组的长度，对数组进行了排序。
• 空间复杂度：O(n)，使用额外的集合存储元素。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestSquareStreak = function (nums) {
	// 用于快速查找
	let numsSet = new Set(nums),
		res = 1;
	// 去重并排序
	nums = [...numsSet].sort((a, b) => a - b);
	for (let num of nums) {
		// 跳过 1
		if (num == 1) {
			continue;
		}
		let len = 1,
			square = num * num;
		while (numsSet.has(square)) {
			len++;
			numsSet.delete(square);
			square *= square;
		}
		res = Math.max(res, len);
	}
	return res == 1 ? -1 : res;
};