148. Two Sum III - Data structure design

Keep a multiplicity map of the numbers seen. add is O(1). For find(value), scan each stored number x and check whether its complement value-x is also present — with a special case when x equals the complement (need at least two copies).

Optimize for frequent adds

Store a hash map count[number] -> how many times it was added. This makes add O(1) and keeps find simple.

find(value)

For each distinct stored number x, its partner is y = value - x:

• if y != x, a pair exists when y is present;
• if y == x, we need two copies of x (count[x] >= 2).

for x in count:
    y = value - x
    if y != x and y in count: return True
    if y == x and count[x] >= 2: return True
return False

Worked example

add(1); add(3); add(5) then:

• find(4): 1 + 3 = 4 → true.
• find(7): pairs are 4, 6, 8 — none equal 7 → false.

Results [null, null, null, null, true, false].

Complexity

• Time: O(1) per add, O(n) per find.
• Space: O(n).

import java.util.*;

class TwoSum {
    private Map<Integer, Integer> count;

    public TwoSum() {
        count = new HashMap<>();
    }

    public void add(int number) {
        count.merge(number, 1, Integer::sum);
    }

    public boolean find(int value) {
        for (int x : count.keySet()) {
            int y = value - x;
            if (y != x && count.containsKey(y)) return true;
            if (y == x && count.get(x) >= 2) return true;
        }
        return false;
    }
}