170. Two Sum III - Data structure design

一刷

We only care about if the occurrence of number is zero or 1 or larger than one. So there's no need to get the number of occurrence out and add 1 to it, we can only put 2 into the hashmap if it already exists.

64.76%

public class TwoSum {
    private HashMap<Integer, Integer> nums;
    public TwoSum() {
        this.nums = new HashMap<Integer, Integer>();
    }
    // Add the number to an internal data structure.
    public void add(int number) {
        // Write your code here
        //Don't care the exact occurance if the number occurs more than once
        nums.put(number, nums.containsKey(number) ? 2 : 1);
    }

    // Find if there exists any pair of numbers which sum is equal to the value.
    public boolean find(int value) {
        // Write your code here
        for (Integer number : nums.keySet()) {
            int residual = value - number;
            if (nums.containsKey(residual) && (number != residual || nums.get(residual) > 1)) return true;
        }
        return false;
    }
}


// Your TwoSum object will be instantiated and called as such:
// TwoSum twoSum = new TwoSum();
// twoSum.add(number);
// twoSum.find(value);

二刷 05/2020

一刷is better

Runtime: 152 ms, faster than 47.15% of Java online submissions for Two Sum III - Data structure design.

Memory Usage: 69.3 MB, less than 25.00% of Java online submissions for Two Sum III - Data structure design.

class TwoSum {

    // Use a hashmap to keep track of all added integers and their count

    // When add, just increment the number count in the hashmap O(1)

    // When find,  iterate through all the keys of the hashmap to find the (value - number) key

    private Map<Integer, Integer> storage;

    public TwoSum() {

        storage = new HashMap<>();

    }

    

    public void add(int number) {

        int cnt = storage.getOrDefault(number, 0);

        storage.put(number, cnt + 1);

    }

    

    public boolean find(int value) {

        int residual;

        for (Integer number : storage.keySet()) {

            residual = value - number;

            if (storage.containsKey(residual)) {

                if (number != residual || storage.get(residual) > 1) {

                    return true;

                }

            }

        }

        return false;

    }

}

/**

 * Your TwoSum object will be instantiated and called as such:

 * TwoSum obj = new TwoSum();

 * obj.add(number);

 * boolean param_2 = obj.find(value);

 */