# 170-two-sum-iii-data-structure-design

## Question

https://leetcode.com/problems/two-sum-iii-data-structure-design/description/

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

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

Example:

find(4) -> true
find(7) -> false

## Thought Process

1. Brute Force - Two Sets (TLE)
1. Use one set to store the numbers, and one set to store the sum
2. Add will take O(n), wrost O(n^2)
3. Find takes O(1)

## Solution

class TwoSum {
Set<Integer> num, sum;

/** Initialize your data structure here. */
public TwoSum() {
num = new HashSet<>();
sum = new HashSet<>();
}

/** Add the number to an internal data structure.. */
if(num.contains(number)){
} else{
Iterator<Integer> iter = num.iterator();
while(iter.hasNext()){
}
}
}

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

/**
* Your TwoSum object will be instantiated and called as such:
* TwoSum obj = new TwoSum();
* boolean param_2 = obj.find(value);
*/
class TwoSum {
Map<Integer, Integer> num;

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

/** Add the number to an internal data structure.. */
num.put(number, num.getOrDefault(number, 0) + 1);
}

/** Find if there exists any pair of numbers which sum is equal to the value. */
public boolean find(int value) {
Iterator<Integer> iter = num.keySet().iterator();
while (iter.hasNext()) {
int num1 = iter.next();
int num2 = value - num1;
if (num.containsKey(num2)) {
if (num1 != num2 || num.get(num2) > 1) return true;
}
}
return false;
}
}

/**
* Your TwoSum object will be instantiated and called as such:
* TwoSum obj = new TwoSum();
* boolean param_2 = obj.find(value);
*/