O(N^2 * log(N)) Solution


  • 0
    E

    The most naive way to solve this problem is to use three nested loops, which gets a timeout from the system. A simple solution in O(N^2 * log(N)) that passed the test is to loop over the first two numbers and search for the third number. If we sort the list in the beginning, we can simply search for the third number using binary search. In order to avoid the duplicates we can use the set from STL, which automatically discarded repeated tuples.

    struct triplet {
        int a, b, c;
        triplet (int aa = 0, int bb = 0, int cc = 0) : a (aa), b (bb), c (cc) {};
        bool operator < (const triplet & tr) const { return std::tie(a,b,c) < std::tie(tr.a,tr.b,tr.c); }
        bool operator == (const triplet & tr) const { return std::tie(a,b,c) == std::tie(tr.a,tr.b,tr.c); }
    };
    
    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int>> ret;
            set<triplet> st;
    
            int i, j;
            sort (nums.begin(), nums.end());
            for (vector<int>::iterator vii = nums.begin(); vii != nums.end(); vii++)
                for (vector<int>::iterator vii2 = vii+1; vii2 != nums.end(); vii2++)
                    if (binary_search(vii2+1, nums.end(), - *vii - *vii2))
                        st.insert (triplet(*vii, *vii2, - *vii - *vii2));
            
            for (set<triplet>::iterator sti = st.begin(); sti != st.end(); sti++)
            {
                vector<int> vi = {sti->a, sti->b, sti->c};
                ret.push_back (vi);
            }
                
            return ret;
        }
    };
    
    // O(N^2 * log(N))
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.