Two Sum III - Data structure design

Design and implement a TwoSum class. It should support the following operations:addandfind.

add- Add the number to an internal data structure. find- Find if there exists any pair of numbers which sum is equal to the value.

Example 1:

add(1); add(3); add(5);
find(4) -> true
find(7) -> false

Example 2:

add(3); add(1); add(2);
find(3) -> true
find(6) -> false

Analysis

Trade Off:

Add vs Find

Approach 1:

using two hashset to store unique number and unique sum when add(), add to unique sum and num, this will have O(n) time for add(), and O(1) for find(). The space complexity though is O(n^2), which unique set for sum will consume O(n^2) space.

Approach 2:

One hashmap for unique numbers, and their count (to tackle multiple duplicate numbers issue)

If it's more add() intensive, then using O(1) time for add(), and O(n) time for find();

if it's more find() intensive, then use O(n) time for add(), and O(1) for find().

Seems that LeetCode's test case tends to have much more add() operations, and approach 1 will have TLE, thus approach 2 is preferred in that case.

几点思考：

1. List的iterator比HashMap的iterator

Solution

Approach 2 - HashMap - Time Complexity: O(n) find, O(1) add, Space Complexity: O(n)

class TwoSum {
    private HashMap<Integer, Integer> map;

    /** Initialize your data structure here. */
    public TwoSum() {
        map = new HashMap<>();
    }

    /** Add the number to an internal data structure.. */
    public void add(int number) {
        map.put(number, map.getOrDefault(number, 0) + 1);
    }

    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int num1 = entry.getKey();
            int num2 = value - num1;
            if ((num1 == num2 && map.get(num2) > 1) || (num1 != num2 && map.containsKey(num2))) {
                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);
 */

Optimized with lower & upper limit

Add low + low2 < value < high + high2 boundary to further reduce the runtime.

class TwoSum {

    Map<Integer,Boolean> map;
    List<Integer> list;
    int low = Integer.MAX_VALUE;
    int high = Integer.MIN_VALUE;
    /** Initialize your data structure here. */
    public TwoSum() {
        map = new HashMap<>();
        list = new LinkedList<>();
    }

    /** Add the number to an internal data structure.. */
    public void add(int number) {
        if(map.containsKey(number)){
            map.put(number,true);
        }else{
            map.put(number,false);
            list.add(number);
            low = Math.min(low,number);
            high = Math.max(high,number);
        }
    }

    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        if(value < 2* low || value > 2*high) return false;
        for(int num : list){
            int target = value - num;
            if(map.containsKey(target)){
                if(num != target) return true;
                else if(map.get(target)) return true;
            }
        }
        return false;
    }
}

Approach 1 - TLE

public class TwoSum {
        Set<Integer> sum;
        Set<Integer> num;

        TwoSum(){
            sum = new HashSet<Integer>();
            num = new HashSet<Integer>();
        }
        // Add the number to an internal data structure.
        public void add(int number) {
            if(num.contains(number)){
                sum.add(number * 2);
            }else{
                Iterator<Integer> iter = num.iterator();
                while(iter.hasNext()){
                    sum.add(iter.next() + number);
                }
                num.add(number);
            }
        }

        // Find if there exists any pair of numbers which sum is equal to the value.
        public boolean find(int value) {
            return sum.contains(value);
        }
    }