频率统计 + 平方扩展 —— 对称子集构造

日期: 2026-06-27
难度: Medium
标签: 哈希表、贪心、数学
题目链接: 3020. 子集中元素的最大数量

题目描述

给一个正整数数组，选一个子集使其元素能排成 [x, x², x⁴, ..., x^k, ..., x⁴, x², x] 的对称模式，求子集的最大元素数量。

第一次思路

第一眼看到提示说用 HashSet，但马上就发现不对——HashSet 去重之后丢掉了每个数出现几次的信息，而这个模式里除了中间元素出现 1 次，其他每个数都需要 2 次（左右对称各一个），所以必须用频率表。

另一个直觉是枚举所有可能的序列长度检查是否能构造，但显然不可行。

最终方案

真正的突破来自两个观察：

平方增长极快——1e9 以内最多平方 5 次就到顶，所以每个起点最多扩展几步就结束了，总复杂度很安全。
对称性决定了构造方式——从最小值 x 向中间贪心扩展，每次消耗 2 个当前值，直到遇到只有 1 个的数作为中心，或到底后回退一步。

算法流程

统计频率表 freq
数字 1 单独处理：1 的平方还是 1，所以全 1 序列长度就是 1 的个数（偶数则减 1，因为序列长度必须奇数）
对每个 x > 1 且 freq[x] ≥ 2：
- 从 x 出发，先消耗 2 个放在两端，len = 2
- 不断检查 next = cur²：
  - 存在且 freq[next] == 1 → 作中心，len += 1，结束
  - 存在且 freq[next] ≥ 2 → 继续对称扩展，len += 2
  - 不存在 → 无法形成对称序列，回退 1，将上一个数作中心
- 更新答案

关键细节

next > 1e9 直接 break（数组里不可能有这个数）
扩展到底后如果 len 是偶数，说明缺中心，len-- 回退
1 和其他数字互斥，不能混在一个序列里

完整代码

第一版

先过了一遍逻辑，代码比较直白：单独循环统计 1，再用另一个 map 统计 > 1 的数，扩展部分用 mp.count() + mp[] 做了两次查找。

class Solution {
public:
    int maximumLength(vector<int>& nums) {
        int num1 = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 1) num1++;
        }
        if (num1 % 2 == 0) num1--;
        int ans = 1;

        unordered_map<int, int> mp;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 1) mp[nums[i]]++;
        }

        for (auto& [k, v] : mp) {
            if (v < 2) continue;

            int len = 2;
            long long temp = k;
            while (true) {
                if (temp * temp > 1e9) break;

                if (mp.count(temp * temp) && mp[temp * temp] == 1) {
                    len++;
                    break;
                }
                if (mp.count(temp * temp) && mp[temp * temp] > 1) {
                    len += 2;
                    temp *= temp;
                } else {
                    break;
                }
            }
            if (len % 2 == 0) len--;
            ans = max(ans, len);
        }
        return max(ans, num1);
    }
};

优化版

几个优化点：

只用一个 freq 表统计所有数，1 的处理也从同一个表里读，省去一次遍历
freq.find() 代替 count + [] 组合，减少哈希表查找次数
统一 int 变量命名，逻辑更紧凑

class Solution {
public:
    int maximumLength(vector<int>& nums) {
        unordered_map<int, int> freq;
        for (int num : nums) freq[num]++;

        int oneCount = freq[1];
        int maxLength = (oneCount % 2 == 0) ? max(1, oneCount - 1) : oneCount;

        for (const auto& [num, count] : freq) {
            if (num == 1 || count < 2) continue;

            long long cur = num;
            int length = 2;
            while (true) {
                long long next = cur * cur;
                if (next > 1e9 || freq.find(next) == freq.end()) break;

                if (freq[next] >= 2) {
                    length += 2;
                    cur = next;
                } else {
                    length += 1;
                    break;
                }
            }
            if (length % 2 == 0) length--;
            maxLength = max(maxLength, length);
        }
        return maxLength;
    }
};

复杂度分析

复杂度	分析
时间复杂度	O(n log C)，C = 1e9，每个起点最多扩展约 5 次。实际遍历一次建表 + 对每个起点扩展几步
空间复杂度	O(n)，哈希表存储每个数的频率

心得总结

对称序列模式 → 非中心元素必须出现 2 次，中心元素 1 次 → 必须用频率表，不能只用 HashSet
平方增长极快 → 扩展深度有限，贪心直接构造即可，无需复杂 DP 或搜索
扩展到底没有中心元素时回退一步——这个细节容易漏，但规律就是奇数长度才有效
1 永远是特例，单独处理