Short and fast C++


  • 8
    class TwoSum {
      unordered_map<int, int> ctr;
    public:
      void add(int number) {
        ctr[number]++;
      }
    
      bool find(int value) {
        for (auto nc : ctr)
          if (ctr.count(value - nc.first) && (nc.first != value - nc.first || nc.second > 1))
            return true;
        return false;
      }
    };
    

    I submitted it several times and most of the time it was faster than all other C++ submissions on the submission detail page. My best was 1292 ms, and the record on the detail page was 1360 ms, achieved by one out of 30 submissions.

    Using count instead of find != end is not only shorter and neater but also significantly faster, and I think the order of the tests also matters a bit. I go through the number/count pairs and first check whether we also have the complementary number. Check whether it's really valid only afterwards. I have to look up the complement anyway, and it almost always fails, so I almost never have to do the rest of the test. The only two times the complement test can succeed are:

    • The rest of the test also succeeds. In this case, we actually have a solution and immediately return.
    • The rest of the test fails. This can only happen once: when the current number is half the target number.

    Update: any_of is kinda neat, but slightly slower:

    bool find(int value) {
      return any_of(ctr.begin(), ctr.end(), [&](pair<int, int> nc){
        return ctr.count(value - nc.first) && (nc.first != value - nc.first || nc.second > 1);
      });
    }

  • 0
    M

    why count operation is faster than find member function do in unordered_map?


  • 0

    I'm not sure, but I'm guessing it's that creating an iterator object is more costly than returning 0 or 1.


  • 1
    N

    I think you only need to test the nc.first * 2 <= value in your ctr, which can make this faster.


  • 0

    I don't see how to make that work. Can you write the whole line?


  • -1
    N

    Here is my code:

    class TwoSum {
    private:
        unordered_map<int, int> num_count;
    
    public:
    
        // Add the number to an internal data structure.
    	void add(int number) {
    	    num_count[number]++;
    	}
    
        // Find if there exists any pair of numbers which sum is equal to the value.
    	bool find(int value) {
    	    for(auto p: num_count) {
    	        // only test the smaller than or equal to half of value part
    	        if(p.first * 2 > value) {
    	            continue;
    	        }
    	        if(num_count.count(value - p.first)) {
    	            if(p.first != value - p.first) {
    	                // found a pair: A + B == value && A != B
    	                return true;
    	            } else if(p.second > 1) {
    	                // found one that A + A == value && there are multiple A's
    	                return true;
    	            }
    	            // otherwise check other pair
    	            // e.g. [2,1,3], find 4
    	        }
    	    }
    	    return false;
    	}
    };

  • 1
    C

    My solution beats 100% of the solutions.(828 ms in CPP)

    Solving this problem is easy. When number is added, store the number in a vector and also increase its count in a map. When we have to find a value, traverse through the vector and see if the difference between the value and the current value is present in the map. If it is present, then the value is found. But sometimes we will unnecessarily traverse the entire vector when we right away know that the sum is not present. This can be avoided by storing the maximum and minimum possible values achievable from the numbers available with us. If the value to found is outside of the range, then return false straight away. This reduces lot of time.

    class TwoSum {
    public:
        unordered_map<int,int> mp;
        vector<int> v;
        int size=0;
        int max1 = 0;
        int max2 = 0;
        int small1 = 0;
        int small2 = 0;
        // Add the number to an internal data structure.
    	void add(int number) {
                // Add the number to the vector
    	    v.push_back(number);
    	    size++;
                // Increase the count of the number in the map.
    	    mp[number]++;
    
                // See if the number is greater than any of the two maximum values. If it is, change them accordingly.
    	    if(number > max1)
    	    {
    	        max2 = max1;
    	        max1 = number;
    	    }
    	    else if(number > max2)
    	    {
    	        max2 = number;
    	    }
    
                // See if the number is smaller than any of the two smallest values. If it is, change the small1 and small2 variables accordingly.
    	    if(number < small1)
    	    {
    	        small2 = small1;
    	        small1 = number;
    	    }
    	    else if(number < small2)
    	    {
    	        small2 = number;
    	    }
    	}
    
        // Find if there exists any pair of numbers which sum is equal to the value.
    	bool find(int value) {
                // If the value is greater than the maximum value achievable, return false
    	    if(value > (max1+max2))
    	    {
    	        return false;
    	    }
                // If the value is smaller than the minimum value achievable, return false
    	    if(value < (small1+small2))
    	    {
    	        return false;
    	    }
    	    for(int i =0;i<size;i++)
    	    {
    	        if(value - v[i] == v[i])
    	        {
    	            if(mp[v[i]] >= 2)
    	            {
    	                return true;
    	            }
    	        }
    	        else
    	        {
    	            if(mp.find(value-v[i]) != mp.end() && mp[value-v[i]] >= 1)
    	            {
    	                return true;
    	            }
    	        }
    	    }
    	    return false;
    	}
    };
    

Log in to reply
 

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