Posted on

Description

Submission I

class TwoSum {
    vector<int> nums;
public:
    /** Initialize your data structure here. */
    TwoSum() {

    }
    
    /** Add the number to an internal data structure.. */
    void add(int number) {
        nums.push_back(number);
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    bool find(int value) {
        sort(nums.begin(), nums.end());
        for(int i = 0, j = nums.size() - 1; i < j; ) {
            int sum = nums[i] + nums[j];
            if(sum < value) ++i;
            if(sum == value) return true;
            if(sum > value) --j;
        }
        return false;
    }
};

/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum* obj = new TwoSum();
 * obj->add(number);
 * bool param_2 = obj->find(value);
 */

Submission II

class TwoSum {
    map<int, int> m;
public:
    /** Initialize your data structure here. */
    TwoSum() {

    }
    
    /** Add the number to an internal data structure.. */
    void add(int number) {
        m[number]++;
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    bool find(int value) {
        for(auto p : m) {
            if(m.find(value - p.first) != m.end()) {
                if(value == 2 * p.first && m[p.first] < 2) return false;
                return true;
            }
        }
        return false;
    }
};

/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum* obj = new TwoSum();
 * obj->add(number);
 * bool param_2 = obj->find(value);
 */

Leave a Reply

Your email address will not be published. Required fields are marked *