2500题里程碑：数学优化与哈希表去重的算法实战复盘

今天刚好刷到了第2500题。这几年基本就写写中等难度的题目，不求突飞猛进，只希望水平别掉得太快。照这个速度，达到3000题的目标感觉遥遥无期。再加上现在AI技术发展这么迅猛，未来会怎样真不好说，就当是且行且珍惜吧。

今天做的题挺有意思，一道是数学推导，另一道考察哈希表的灵活运用。正好分享一下我的解题思路。

3857. 拆分到1的最小总代价

这道题题意是：给定整数 n，你可以执行操作将整数 x 拆成两个正整数 a 和 b（满足 a+b=x），代价为 a*b。最终目标是把 n 拆分成 n 个 1，求最小总代价。

题目给出的 n=4 的例子有点迷惑性。

这让我想起一个经典的小学问题：周长固定时，什么形状的长方形面积最大？答案是正方形。如果要求边长是整数，那就是让两条边尽可能接近。

具体的数学证明这里就不展开了。回到这个问题，条件相当于 a + b = x 是固定的，我们要让代价 a * b 尽量小。根据上面的结论，应该让 a 和 b 的差值尽可能大。所以每次拆分的最优策略就是拆成 1 和 x-1，这样单次代价是 1 * (x-1) = x-1。

那么，从 n 一路拆到 1 的过程，总代价就是一个等差数列求和：
(n-1) + (n-2) + ... + 1 = n * (n-1) / 2。

代码实现就一行：

class Solution {
public:
    int minCost(int n) {
        return n * (n-1) / 2;
    }
};

3396. 使数组元素互不相同所需的最少操作次数

这道题是简单题，主要是因为数据范围小（n <= 100），可以用 O(n^2) 的模拟通过。如果数据范围扩大到 1e5，就变成了下面这道中等题。两道题的本质是一样的，所以这里直接讨论更优的 O(N) 解法。

下面是它的升级版，3779. 得到互不相同元素的最少操作次数：

我提供了两种 O(N) 的思路。

做法1：正向模拟 + 哈希表

这种涉及统计元素个数的题目，很自然想到用哈希表。思考一下，最终满足条件的数组是什么样？所有元素都只出现一次。如果用 unordered_map 记录每个元素的出现次数，那么最终状态就是 map 的 size 和剩余数组的长度相等。

所以正向模拟的过程就是：

1. 先统计整个数组的词频。
2. 从数组开头开始，每次移除3个元素（不足3个则全删），并更新map中的计数。
3. 当map.size() 等于剩余数组长度时，说明剩下的元素已经互不相同，停止操作。操作次数即为答案。

需要注意两点：

• 当map中某个key对应的value减到0时，需要手动erase掉这个key，否则它仍然会占用size。
• 要小心数组越界，当剩余长度不足3时直接算作一次操作并结束。

class Solution {
public:
    int minOperations(vector<int>& nums) {
        unordered_map<int, int> cnt;
        for(auto x : nums) {
            cnt[x]++;
        }
        int ans = 0, now = 0, remain = nums.size();
        while(cnt.size() != remain) {
            if(remain < 3) {
                ans++;
                break;
            }
            for(int i = 0; i < 3; i++) {
                remain--;
                int tmp = nums[now];
                cnt[tmp]--;
                if(cnt[tmp] == 0) cnt.erase(tmp);
                now++;
            }
            ans++;
        }
        return ans;
    }
};

做法2：逆向寻找最长合法后缀

因为题目规定只能从数组开头移除元素，所以最终保留下来的，一定是原数组的一个后缀。问题可以转化为：寻找最长的、元素互不重复的后缀。这个后缀之前的所有元素都需要被删除。

实现上，我们从数组末尾向前遍历，用一个unordered_set记录已经出现过的元素。当遇到一个元素在set中已经存在时，说明重复出现了，遍历停止。此时，当前下标i及之前的所有元素都需要被移除。由于每次操作删3个，所需的操作次数就是 (i / 3) + 1。如果整个数组都没有重复，则不需要操作。

这种方法通常比方法一更快，因为它不需要在map中反复插入和删除。

class Solution {
public:
    int minOperations(vector<int>& nums) {
        unordered_set<int> seen;
        for (int i = nums.size() - 1; i >= 0; i--) {
            if (seen.count(nums[i])) { // nums[i] 在 seen 中
                return i / 3 + 1;
            }
            seen.insert(nums[i]);
        }
        return 0;
    }
};

两种方法的时间复杂度都是 O(N)。方法一需要重复更新哈希表，开销稍大；方法二在一般情况下不需要遍历整个数组，效率更高。在算法题中，灵活运用哈希表的特性往往能简化问题。

刷题不仅是练习代码，更是锻炼一种将复杂问题抽象、分解并寻找规律的能力。希望今天的分享对你有用，也欢迎到 云栈社区 一起交流更多解题心得。