package leetcode;

import java.util.*;

/*

Design and implement a TwoSum class.

It should support the following operations: add and find.

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.

For example,

add(1); add(3); add(5);

find(4) -> true

find(7) -> false

*/

class TwoSum3{

private List<Integer> list = new ArrayList<Integer>();

private Map<Integer, Integer> map = new HashMap<Integer, Integer>();

// Add the number to an internal data structure.

public void add(int number) {

if (map.containsKey(number)) map.put(number, map.get(number) + 1);

else {

map.put(number, 1);

list.add(number);

}

}

// Find if there exists any pair of numbers which sum is equal to the value.

public boolean find(int value) {

for (int i = 0; i < list.size(); i++){

int num1 = list.get(i), num2 = value - num1;

if ((num1 == num2 && map.get(num1) > 1) || (num1 != num2 && map.containsKey(num2))) return true;

}

return false;

}

public static void main(String[] args) {

TwoSum3 ts3 = new TwoSum3();

ts3.add(1);

ts3.add(3);

ts3.add(5);

System.out.println(ts3.find(1));

System.out.println(ts3.find(4));

System.out.println(ts3.find(7));

System.out.println(ts3.find(8));

ts3.add(2);

System.out.println(ts3.find(7));

}

}