三数之和问题中动态规划的权衡及自底向上实现求助

一、动态规划在三数之和里的取舍 #

用DP解三数之和，核心是这几个trade-off：

• 时间vs空间：你写的自顶向下递归没加记忆化，会有大量重复计算直接超时；但加记忆化或者用自底向上，就得开空间存状态（比如记录「处理到第i个元素、已选k个数、剩余目标值为t」的所有组合），空间开销会飙升，尤其是数组里有负数时，目标值的范围会很大，内存占用会很夸张。
• 去重麻烦：三数之和要求结果不重复，DP的状态里没法直接过滤重复组合，得额外做去重处理，要么在状态设计里额外考虑，要么最后用集合去重，比双指针的去重逻辑复杂得多。
• 状态定义绕：要把「当前索引、已选数量、剩余目标」这三个维度的状态理清楚，还要处理边界（比如选够3个数、索引越界），逻辑上比双指针绕很多，容易出错。
• 实际效率不如双指针：LeetCode上三数之和的最优解是双指针，时间O(n²)，空间O(logn)（排序开销）；DP就算优化到O(n²)，常数项也比双指针大，实际运行起来未必更快，甚至可能更慢。

二、自底向上的DP实现 #

先明确：自底向上的核心是从数组末尾往前推，记录每个位置开始选k个数、剩余目标为t的所有组合，逐步合并出结果。而且必须先排序，才能方便去重。

C++代码实现 #

#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> result;
    int n = nums.size();
    if (n < 3) return result;
    sort(nums.begin(), nums.end());

    // next_dp[k][t]：从下一个索引开始，选k个数，剩余目标为t的所有组合列表
    vector<unordered_map<int, vector<vector<int>>>> next_dp(4);
    next_dp[0][0] = {{}}; // 初始状态：选0个数，剩余目标0，只有空组合

    for (int i = n - 1; i >= 0; --i) {
        // 去重：跳过和后一个元素相同的，避免重复组合
        if (i < n - 1 && nums[i] == nums[i+1]) {
            continue;
        }
        // 复制next_dp作为当前dp的初始状态（不选当前元素的情况）
        vector<unordered_map<int, vector<vector<int>>>> curr_dp = next_dp;

        // 处理选当前元素的情况：从选0、1、2个数的状态推导选1、2、3个数的状态
        for (int count = 2; count >= 0; --count) {
            for (auto& [target, groups] : next_dp[count]) {
                int new_target = target - nums[i];
                for (auto& group : groups) {
                    vector<int> new_group = group;
                    new_group.push_back(nums[i]);
                    curr_dp[count + 1][new_target].push_back(new_group);
                }
            }
        }

        // 收集当前能凑成和为0的三元组
        if (curr_dp[3].find(0) != curr_dp[3].end()) {
            for (auto& triplet : curr_dp[3][0]) {
                result.push_back(triplet);
            }
        }

        next_dp = move(curr_dp);
    }

    // 因为是从后往前加元素，三元组是逆序的，反转成正常顺序
    for (auto& triplet : result) {
        reverse(triplet.begin(), triplet.end());
    }

    // 最后再去重一次，确保没有遗漏的重复组合
    set<vector<int>> unique_set(result.begin(), result.end());
    result.assign(unique_set.begin(), unique_set.end());

    return result;
}

说明 #

这个写法用滚动数组优化了空间（只用curr_dp和next_dp两个状态数组），但空间开销还是比双指针大很多。而且实际运行中，因为要存储大量组合列表，运行速度未必比加了记忆化的自顶向下快，甚至可能还是超时——毕竟DP不是三数之和的最优解法，LeetCode上更推荐用双指针。

三、你的递归解法超时原因 #

你的递归只做了元素去重，但没加记忆化，导致相同的「index、count、target」状态被反复计算，比如不同的路径会多次处理同一个位置、选同样数量的数、剩余同样目标的情况，重复递归直接导致超时。如果要救这个递归，加个备忘录（比如unordered_map或者三维数组）存储已经计算过的状态对应的组合，就能避免重复计算了。

内容的提问来源于stack exchange，提问作者Sanjay Soni