目标
给你一个 正整数 数组 nums 。
你需要从数组中选出一个满足下述条件的子集：
- 你可以将选中的元素放置在一个下标从 0 开始的数组中，并使其遵循以下模式：[x, x^2, x^4, ..., x^k/2, x^k, x^k/2, ..., x^4, x^2, x]（注意，k 可以是任何 非负 的 2 的幂）。例如，[2, 4, 16, 4, 2] 和 [3, 9, 3] 都符合这一模式，而 [2, 4, 8, 4, 2] 则不符合。
返回满足这些条件的子集中，元素数量的 最大值 。
示例 1：
输入：nums = [5,4,1,2,2]
输出：3
解释：选择子集 {4,2,2} ，将其放在数组 [2,4,2] 中，它遵循该模式，且 22 == 4 。因此答案是 3 。示例 2：
输入：nums = [1,3,2,4]
输出：1
解释：选择子集 {1}，将其放在数组 [1] 中，它遵循该模式。因此答案是 1 。注意我们也可以选择子集 {2} 、{4} 或 {3} ，可能存在多个子集都能得到相同的答案。说明：
- 2 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9
思路
将正整数数组 nums 的子序列按照模式放入一个下标从 0 开始的数组中，模式为 [x x^2 x^4 x^8 ... x^k/2 x^k x^k/2 ... x^8 x^4 x^2 x]，k 可以是任何非负的 2 的幂，即 1、2、4、8、16……。求满足条件的子序列的最大长度。
对数组中的元素计数，如果 x 出现次数大于等于 2 则开始倍增，将长度加 2，判断 x^2 是否出现，如果出现次数大于 1，则判断 (x^2)^2 是否出现，以此类推。循环结束时判断数字的出现次数，如果为 0 需要将前面的元素作为中间元素，之前长度加了 2 这里需要减 1，如果为 1 正好作为中间元素将长度加 1。
代码
/**
* @date 2026-06-29 17:33
*/
public class MaximumLength3020 {
public int maximumLength(int[] nums) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int num : nums) {
cnt.merge(num, 1, Integer::sum);
}
int res = 1;
if (cnt.get(1) != null) {
res = Math.max(res, cnt.get(1) - (1 - cnt.get(1) % 2));
cnt.remove(1);
}
for (Integer num : cnt.keySet()) {
int l = 0;
while (cnt.getOrDefault(num, 0) > 1) {
l += 2;
num *= num;
}
res = Math.max(res, l + (cnt.get(num) == null ? -1 : 1));
}
return res;
}
}
性能
