I am doing the 3Sum problem: https://leetcode.com/explore/interview/card/top-interview-questions-medium/103/array-and-strings/776/

Question in brief: Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] nums[j] nums[k] == 0. Notice that the solution set must not contain duplicate triplets.

My problem: I have a solution which does return some but not all possible triplets, and I don't understand where I am going wrong. Secondly, my algorithm is O(N^2 log N), any recommendation on improving it is welcome.

Input:
[-1,0,1,2,-1,-4,-2,-3,3,0,4]
Output:
[[-3,-1,4],[-3,0,3],[-4,1,3],[-2,0,2],[-4,0,4]]
Expected:
[[-4,0,4],[-4,1,3],[-3,-1,4],[-3,0,3],[-3,1,2],[-2,-1,3],[-2,0,2],[-1,-1,2],[-1,0,1]]

Algorithm: I have included my algorithm in the code along with comments, but here is the gist- For each pair of numbers I store their sum as a key and the indices of the numbers that give me that sum as the value. Then in a loop I go through each element and check if the difference between target value and that number is present as a key in the map. If it is, and all indices are unequal, I add it to a vector that is ultimately returned.

Code:

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

vector<vector<int>> threeSum(vector<int> &nums) {
    /*
     * If less than 3 elements are passed return empty vector
     */
    if (nums.size() < 3)
        return {};

    int target = 0; // all three numbers sum up to 0 as given
    vector<vector<int>> outer; // this is returned by the function
    unordered_map<int, vector<int>> umap; // unordered_map for keeping sum and indices

    /*
     * Calculate sum of each pair of numbers
     * Store the sum as key and the pair as value
     * i != j is guaranteed
     */
    for (int i = 0; i < nums.size(); i  )
        for (int j = i   1; j < nums.size(); j  )
            umap[nums[i]   nums[j]] = {i, j};

    /*
     * Go through each element and calculate the difference
     * between target and that element, this gives the sum
     * of the other two elements.
     * Look for the sum in unordered_map
     * If it is present check if all three indices are not equal to each other
     */
    for (int i = 0; i < nums.size(); i  ) {
        vector<int> inner;
        int diff = target - nums[i];
        auto it = umap.find(diff);
        inner = umap[diff];
        if (it != umap.end() && i != inner[0] && i != inner[1]) {
            inner.push_back(i);
            vector<int> tmp;
            for (auto &j: inner)
                tmp.push_back(nums[j]); // push actual numbers instead of indices
            sort(tmp.begin(), tmp.end()); // sort the inner three elements
            if (find(outer.begin(), outer.end(), tmp) == outer.end()) // for removing duplicates
                outer.push_back(tmp);
        }
    }
    return outer;
}

int main() {
    vector<int> v{-1, 0, 1, 2, -1, -4, -2, -3, 3, 0, 4};
    vector<vector<int>> ret = threeSum(v);
    for (auto &i: ret) {
        for (auto j: i)
            cout << j << " ";
        cout << endl;
    }
}

CodePudding user response：

Your bug is demonstrated with the input [-5, 1, 2, 3, 4].

The problem is that 5 == 1 4 == 2 3. Your map will only store one of those pairs as the value for that key, and it therefore does not record the fact that BOTH pairs can lead to that key.

CodePudding user response：

Since you asked for improvements how about this algorithm:

create an std::unordered_map<int, int> mapping each input to the number of occurances. Then:

for (const auto & it = map.begin(); it != map.end();   it) {
    for (const auto & it2 = it; it2 != map.end();   it2) {
        auto it3 = map.find(-*it - *it2);
        if (it3 != map.end()) {
            it ((*it > *it3) || (*it2 > *it3)) continue;
            if (it == it2) {
                if (it == it3) {
                   if (it.second > 2) cout << *it << ", " *it2 << ", " << *it3 << std::endl;
                } else {
                   if (it.second > 1) cout << *it << ", " *it2 << ", " << *it3 << std::endl;
                }
            } else if (it2 == it3) {
                if (it2.second > 1) cout << *it << ", " *it2 << ", " << *it3 << std::endl;
            } else {
                cout << *it << ", " *it2 << ", " << *it3 << std::endl;
            }
        }             
    }
}

That should be O(n^2) without duplicates.