My solutions in Java, C++, and Python. O(1) time for add, O(n) time for find, O(n) space


  • 39

    I use HashMap to store times of number be added.

    When find be called, we iterate the keys of HashMap, then find another number minus by value.
    Then combine the detections together.

    Java:

    public class TwoSum {
        private HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    
        public void add(int number) {
            map.put(number, map.containsKey(number) ? map.get(number) + 1 : 1);
        }
    
        public boolean find(int value) {
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                int i = entry.getKey();
                int j = value - i;
                if ((i == j && entry.getValue() > 1) || (i != j && map.containsKey(j))) {
                    return true;
                }
            }
            return false;
        }
    }
    

    C++:

    class TwoSum {
        unordered_map<int,int> map;
    public:
        void add(int number) {
            map[number]++;
        }
    
        bool find(int value) {
            for (unordered_map<int,int>::iterator it = map.begin(); it != map.end(); it++) {
                int i = it->first;
                int j = value - i;
                if ((i == j && it->second > 1) || (i != j && map.find(j) != map.end())) {
                    return true;
                }
            }
            return false;
        }
    };
    

    Python:

    class TwoSum:
    
        # initialize your data structure here
        def __init__(self):
            self.table = dict()
    
        # @return nothing
        def add(self, number):
            self.table[number] = self.table.get(number, 0) + 1;
    
        # @param value, an integer
        # @return a Boolean
        def find(self, value):
            for i in self.table.keys():
                j = value - i
                if i == j and self.table.get(i) > 1 or i != j and self.table.get(j, 0) > 0:
                    return True
            return False

  • 0
    H

    Hello , thank you for sharing.
    Actually I used similar approach, the only difference is that I used 0 to mark the first appearence of a value, and then something goes wrong. I tried to modify the "1" to "0" in your code and submit, the same problem (wrong answer)appears. Passed when I use "1". Do you have any ideas for this issue? Thanks.
    Here's my code:

    class TwoSum {
    private:
    unordered_map<int, int> m;
    public:
    void add(int number) {
        m[number]= m.find(number)==m.end() ? 0 : m[number]+1;
    }
    bool find(int value) {
        unordered_map<int, int>::iterator itr;
        for(itr=m.begin(); itr!=m.end(); itr++){
            int v = value - itr->first;
            if(m.find(v) == m.end())continue;
            if(itr->first == v && itr->second==0)continue;
            return true;
        }
        return false;
    }
    

    };


  • 0

    Because in C++, m[0] == 0 is true even if "0" is not the key.

    In other words if you set "0" as first appearance, you can't know whether the key exist once or not, because the value is also "0" even if key haven't inserted .

    I update my C++ solution to make add looks simple.
    But in Java you can set the first appearance value to 0 and detect it correctly.
    Please tell me if you have further question.


  • 1
    H

    Thank you for your answer. I found that in the expression:
    m[number]= m.find(number)==m.end() ? 0 : m[number]+1;
    m.find(number)==m.end() is always false, so on its first appearance, m[number] is always set to 1
    I think that maybe m[number] on the left of the expression would firstly create the key (whose value is set to 0) to receive new value.
    So I modified my code as fellows:

    void add(int number) {
    int counter = m.find(number)==m.end() ? 0 : m[number]+1;
    m[number] = counter;
    }


  • 0
    L
    This post is deleted!

  • 0

    Please make sure you understand this problem correctly.


  • 7
    W

    Thanks for sharing. I made some optimization to your Java solution and improved the execution time from 360ms to 333ms:

    public class TwoSum {
    
    	Hashtable<Integer, Integer> lTable = new Hashtable<Integer, Integer>();
    
    	public void add(int number) {
    		// Since this is two sum, we actually do not need the count over 2.
    		lTable.put(number, lTable.get(number) == null ? 1 : 2);
    	}
    
    	public boolean find(int value) {
    		for (int key : lTable.keySet()) {
    			int res = value - key;
    			Integer occr = lTable.get(res);
    			if (occr != null && (occr == 2 || (occr == 1 && key != res))) {
    				return true;
    			}
    		}
    		return false;
    	}
    }

  • 0
    B

    How did you make you Python solution get rid of the "Time Limit Exceeded" error?
    I tried use list, dict, and copied your dict solution as well. All of them failed with the "Time Limit Exceeded" error.


  • 0

    I don't know, probably they change test envrionment or test cases.


  • 0
    B

    I think either they mis-calculated the loop in find() O(nn) time complexity , or they want an O(1) solution.


  • 0

    There're only one possible O(1) solution for find, pre-calculate all possible result. But it causes add to be O(n^2). So it's not doable.


  • 0

    The reason of Python code can not pass is: the dict resize in Python. Probably Python's memory management is not efficient.

    If you wanna fix this, you may need implement a dict that can set initial capacity.

    Please refere below links:

    http://www.laurentluce.com/posts/python-dictionary-implementation/
    http://stackoverflow.com/questions/1298636/how-to-set-initial-size-for-a-dictionary-in-python


  • 0

    Great observation that we do not need to count over 2 :-)


  • 0

    Hi, huilong. Have you got your above code accepted? Even modified as you wrote in the comment, the code meets TLE. In fact, you can just count the number of appearances. The code will become much easier.

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

  • 0

    @jianchao.li.fighter
    Shorter and apparently also faster:

    if ((first != second && data.count(second)) || (first == second && data[first] > 1))
    

    Even shorter and I think also even a bit faster:

    if (data.count(second) && (first != second || data[first] > 1))
    

    You have to look up second anyway. And it's best to do it first, because it almost always fails, so the rest of the test almost never gets tested. In your version, you always test something before looking up second anyway. Granted, my version might look it up twice for one first/second pair, but only for one (when first is number/2).


  • 0

    Hi, Stefan. Thank you for your nice suggestions about refining the code. I try it and it actually runs faster (from 1416ms to 1376ms, much closer to the fastest of C++) :-)


  • 0
    C

    instead, maybe it was because the code used self.table.keys() rather than self.table?


  • 0
    This post is deleted!

  • 0

    You can easily make your Python solution not just accepted but one of the fastest solutions if you just use table and do the main test j in table first.

    Before:

    for i in self.table.keys():
        j = value - i
        if i == j and self.table.get(i) > 1 or i != j and self.table.get(j, 0) > 0:
    

    After:

    table = self.table
    for i in table:
        j = value - i
        if j in table and (i == j and table.get(i) > 1 or i != j and table.get(j, 0) > 0):
    

    The expression can be shortened now, but I'll leave that up to you if you want :-) Anyway, for an even faster solution, see here.


  • 0

    Yes, you are right. Does the dict.get(i) and i in dict have different implementation?


Log in to reply
 

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