Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save BiruLyu/97f97b795673e4cd06843ffcee2cd9e5 to your computer and use it in GitHub Desktop.
Save BiruLyu/97f97b795673e4cd06843ffcee2cd9e5 to your computer and use it in GitHub Desktop.
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);
}
}
public class TwoSum {
private HashMap<Integer, Integer> dict; // using map instead of set is because allowing repetition
private List<Integer> nums;
/** Initialize your data structure here. */
public TwoSum() {
dict = new HashMap<Integer, Integer>();
nums = new ArrayList<Integer>();
}
/** Add the number to an internal data structure.. */
public void add(int number) {
if(dict.containsKey(number)){
dict.put(number, dict.get(number) + 1);
} else {
nums.add(number);
dict.put(number, 1);
}
}
/** 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 < nums.size(); i++){
int num1 = nums.get(i);
int num2 = value - num1;
if(num1 == num2 && dict.get(num1) > 1) return true;
if(num1 != num2 && dict.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);
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment