LeetCode 15：使用哈希映射的 3Sum

Question

我用 cpp 编写了代码，但它没有给出正确的输出。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> v;
        if(nums.size()==0)
        {
            return v;
        }
        for(int i=0;i<nums.size()-1;i++)
        {
            set<int> s;
            for(int j=i+1;j<nums.size();j++)
            {
                int currsum = 0-nums[i]-nums[j];
                if(s.find(currsum)!=s.end())
                {
                    v.push_back(vector<int> ({nums[i], nums[j],currsum}));
                    break;
                }
                else
                    s.insert(nums[j]);
            }
        }
        return v;
    }
};

这与leetcode中的测试用例不同

请帮忙！

Answer 1

我想这将是一个 O(N ^ 2) 的有效解决方案，它通过了 LeetCode 的 "Online Judge":

class Solution {
public:
    vector<vector<int>> threeSum(vector<int> &nums) {
        vector<vector<int>> triplets;

        std::sort(nums.begin(), nums.end());

        for (int index = 0; index < nums.size(); index++) {
            int target = -nums[index];
            int lo = -~index, hi = nums.size() - 1;

            if (target < 0)
                break;

            while (lo < hi) {
                int sum = nums[lo] + nums[hi];

                if (sum < target)
                    lo++;

                else if (sum > target)
                    hi--;

                else {
                    vector<int> triplet(3, 0);
                    triplet[0] = nums[index];
                    triplet[1] = num[lo];
                    triplet[2] = num[hi];
                    triplets.push_back(triplet);

                    while (lo < hi && nums[lo] == triplet[1])
                        lo++;

                    while (lo < hi && nums[lo] == triplet[2])
                        hi--;
                }
            }

            while (-~index < nums.size() && nums[-~index] == nums[index])
                index++;
        }

        return triplets;
    }
};

这里是 LeetCode 的解决方案之一（也是 O(N ^ 2)）：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        set<pair<int, int>> found; // or define hash<pair<int, int>> and use unordered_set.
        unordered_set<int> dups;
        unordered_map<int, int> seen;

        for (int i = 0; i < nums.size(); ++i)
            if (dups.insert(nums[i]).second)
                for (int j = i + 1; j < nums.size(); ++j) {
                    int complement = -nums[i] - nums[j];
                    auto it = seen.find(complement);

                    if (it != end(seen) && it->second == i) {
                        int v1 = min(nums[i], min(complement, nums[j]));
                        int v2 = max(nums[i], max(complement, nums[j]));

                        if (found.insert({v1, v2}).second)
                            res.push_back({nums[i], complement, nums[j]});
                    }

                    seen[nums[j]] = i;
                }

        return res;
    }
};

LeetCode 15：使用哈希映射的 3Sum

LeetCode 15: 3Sum using hash maps

c++

algorithm

big-o

hashmap

参考