Hashmap c++ solution, quadratic time, 72ms


  • 0
    C

    I assume all the solutions are like (x, y, z) and x <= y <= z, so no duplicate.

    First scan the array into a map, so the keys are sorted.
    Then outer loop the first element x, and inner loop the second y, and use map to find z.

    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int>> result(0);
            // scan the array into a map, record the occurrence
            map<int, int> m;
            for (int i = 0; i < nums.size(); ++i){
                if (m.find(nums[i]) == m.end()) m[nums[i]] = 1;
                else ++m[nums[i]];
            }
            
            typedef map<int, int>::iterator map_it;
            // OUTER LOOP on x, start from the front
            for (map_it iter = m.begin(); iter != m.end(); ++iter){
                if (iter->first > 0) break;  // if the minimum is greater than 0, no more solutions
                iter->second -= 1;           // keep track on the occurrence
                // INNER LOOP on y, start from where x stays
                for (map_it jter = iter; jter != m.end(); ++jter){  
                    if (jter->second == 0) continue;         // no more to use, continue
                    int z = -(iter->first + jter->first);     
                    jter->second -= 1;                       // keep track on the occurrence
                     // if we find the third elem, make sure it's max, and it's ok to use
                    map_it temp = m.find(z);
                    if (temp != m.end()){      
                        if (z >= jter->first && temp->second != 0) {  
                            result.push_back({iter->first, jter->first, z});
                        }
                    }
                    jter->second += 1;      // recover the occurrence
                }
                iter->second += 1;          // recover the occurrence
            }
            return result;
        }
    };

  • 0
    Z

    so your time complexity is nlogn + (n^2)logn ?


  • 0
    C

    right..right..searching for the 3rd elem takes logn in a treemap, so n^2 * logn, not cool, not cool at all. Thanks man


Log in to reply
 

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