c++ - C++ 3sum复杂度

Question

我正在尝试解决cpp中的3和问题。

给定一个n个整数的数组S，S中是否有元素a，b，c使得a + b + c = 0？在给出零总和的数组中找到所有唯一的三元组。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int size = nums.size();
        vector<vector<int>> result;
        for (int i = 0; i < size - 2; ++i) {
            for (int j = i + 1; j < size - 1; ++j) {
                for (int k = j + 1; k < size; ++k) {
                    if (sumToZero(i, j, k, nums)) {
                        vector<int> newComb = vectorify(i, j, k, nums);
                        //printComb(newComb);
                        if (!exist(newComb, result)) {
                            //cout << "not exist" << endl;
                            result.push_back(newComb);
                        } else {
                            //cout << "exist" << endl;
                        }
                    }
                }
            }
        }
        return result;
    }

    bool sumToZero(int i, int j, int k, vector<int>& nums) {
        return nums[i] + nums[j] + nums[k] == 0;
    }

    vector<int> vectorify(int i, int j, int k, vector<int>& nums) {
        vector<int> result;
        result.push_back(nums[i]);
        result.push_back(nums[j]);
        result.push_back(nums[k]);
        return result;
    }

    void printComb(vector<int>& input) {
        cout << input[0] << input[1] << input[2] << endl;
    }

    bool isSameComb(vector<int>& a, vector<int> b) {
        for (int i = 0; i < b.size(); ++i) {
            if (a[0] == b[i]) {
                b.erase(b.begin() + i);
            }
        }
        for (int i = 0; i < b.size(); ++i) {
            if (a[1] == b[i]) {
                b.erase(b.begin() + i);
            }
        }
        for (int i = 0; i < b.size(); ++i) {
            if (a[2] == b[i]) {
                b.erase(b.begin() + i);
            }
        }
        return b.empty();
    }

    bool exist(vector<int>& niddle, vector<vector<int>>& haystack) {
        int size = haystack.size();
        for (int i = 0; i < size; ++i) {
            if (isSameComb(niddle, haystack[i])) {
                return true;
            }
        }
        return false;
    }
};

但是，此解决方案超出了时间限制。我想不出额外复杂性的根源。有人可以帮我指出我在哪里做额外的计算吗？

Answer 1

您可以在O(n²)中输入以下内容:

std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
    std::sort(nums.begin(), nums.end());

    std::vector<std::vector<int>> res;
    for (auto it = nums.begin(); it != nums.end(); ++it) {
        auto left = it + 1;
        auto right = nums.rbegin();
        while (left < right.base()) {
            auto sum = *it + *left + *right;
            if (sum < 0) {
                ++left;   
            } else if (sum > 0) {
                ++right;   
            } else {
                res.push_back({*it, *left, *right});
                std::cout << *it << " " <<  *left << " " << *right << std::endl;
                ++left;
                ++right;
            }
        }
    }
    return res;
}

Demo

我把重复处理作为练习。