leetcode/F15_3Sum

给一个数组, 求其中三数和为零的所有组合, 要求不能重复

思路:

遍历数组, 找出所有三数集合, 再判断是否为零, 之后用一个map去重

代码:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        if (nums.size() < 3) return {};

        vector<vector<int>> result;
        map<int, bool> repetitive;

        for (int i = 0; i < nums.size() - 2; ++i)
            for (int k = i + 1; k < nums.size() - 1; ++k)
                for (int v = k + 1; v < nums.size(); ++v) {
                    if (nums[i] + nums[k] + nums[v] != 0) continue;
                    else {
                        int nmax = max(nums[i], nums[k]);
                        nmax = max(nmax, nums[v]);
                        int nmin = min(nums[i], nums[k]);
                        nmin = min(nmin, nums[v]);

                        if (!repetitive[(nmax << 4) + nmin]) {
                            repetitive[(nmax << 4) + nmin] = true;
                            result.push_back({ nmin, 0 - nmin - nmax, nmax });
                        }
                        else continue;
                    }
                }

        return result;
    }
};

实际上map去重那里有漏洞, “精心准备”的数字有可能骗过它

结果:

超时了, 看到那密密麻麻的红字, 感觉有点不妙

实测算法在数组长度为200时已经有明显的停顿

算法复杂度大概是 差不多O(n3) 的样子, 所以随着长度的增加, 时间复杂度的增加是很恐怖的

200有明显停顿的话. 3000大概能算个痛

那么得优化算法了, 怎么优化呢? 暂时想不到…

优化的想法:

现在的算法在第一次循环的时候会将下标[0, 1]和后续所有的下标组合

第二次循环的时候会将下标[1, 2]和后续所有下标组合

这里明显有可以提升的空间, 因为两次里面1重叠了, 同理, 后续的组合都有重叠

在200长度的算法中, 大致会有 4000000 次循环, 而最后的结果只有 6 个组合

想要优化的话应该从这里入手, 如何在逻辑上筛除掉一些可能但和又不为零的组合

怎么删除? emmmm… 想不到