C++ 3sum 复杂度 [英] C++ 3sum complexity

问题描述

我试图解决 cpp 中的 3 sum 问题.

I was trying to solve the 3 sum problem in cpp.

给定一个由 n 个整数组成的数组 S，S 中是否有元素 a、b、c 使得 a + b + c = 0?找出数组中所有唯一的三元组，其总和为零.

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

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;
    }
};

但是，这个解决方案超出了时间限制.我想不出额外复杂性的来源.有人能帮我指出我在哪里做额外的计算吗?

However, this solution exceeded the time limit. I cannot think of the source of extra complexity. Can someone help me point out where am I doing extra computation?

推荐答案

您可以在 O(n²) 中使用以下内容:

You can be in O(n²) with something like:

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;
}

演示

我把重复处理当作练习.

I let duplicate handling as exercise.

这篇关于C++ 3sum 复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！