问题描述
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
解决思路
- 创建HashMap,将number和numbe出现的次数，分别作为HashMap的key-value键值对
- 如果HashMap中不存在numbe，则numbe出现的次数设为1；若出现过，则次数自增1一次
- 在寻找是否有两个number相加为value时，分num1，num2相等和不相等两种情况
- 若相等，则他们出现的次数应该大于1（即有两个），才能return true，否则只有一个，不满足题目要求（一个数不能重复使用）
- 若不相等，则HashMap应当包含num2（value - num1）,return true
- 以上条件都不满足，return false
代码
package leetcode;
import java.util.HashMap;
import java.util.Map;
public class TwoSumIII {
Map<Integer, Integer> map;
/*Initialization your data structure here*/
public TwoSumIII(){
map = new HashMap<>();
}
/*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);
}
}
/*Find if there exists any pair of numbers which sum is equal to the value*/
public boolean find(int value){
for (int i: map.keySet()) {
int num1 = i, num2 = value - num1;
//num1 == num2 OR num1 != num2
if ((num1 == num2 && map.get(num1) > 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();
*/
}
