设计并实现一个 TwoSum 类。他需要支持以下操作:add 和 find。
add -把这个数添加到内部的数据结构。
find -是否存在任意一对数字之和等于这个值
在线评测地址：
LintCode 领扣
样例 1:
add(1);add(3);add(5);
find(4)//返回true
find(7)//返回false
【题解】
使用哈希表的方法是最快的。
add 可以做到 O(1)
find 可以做到 O(n)
public class TwoSum {
private Map<Integer, Integer> counter;
public TwoSum() {
counter = new HashMap<Integer, Integer>();
}
// Add the number to an internal data structure.
public void add(int number) {
counter.put(number, counter.getOrDefault(number, 0) + 1);
}
// Find if there exists any pair of numbers which sum is equal to the value.
public boolean find(int value) {
for (Integer num1 : counter.keySet()) {
int num2 = value - num1;
int desiredCount = num1 == num2 ? 2 : 1;
if (counter.getOrDefault(num2, 0) >= desiredCount) {
return true;
}
}
return false;
}}
// Your TwoSum object will be instantiated and called as such:// TwoSum twoSum = new TwoSum();// twoSum.add(number);// twoSum.find(value);
排序数组+双指针的算法会超时，但是大家可以看看是怎么写的，时间复杂度：
add O(n)
find O(n)
public class TwoSum {
public List<Integer> nums;
public TwoSum() {
nums = new ArrayList<Integer>();
}
public void add(int number) {
nums.add(number);
int index = nums.size() - 1;
while (index > 0 && nums.get(index - 1) > nums.get(index)) {
int temp = nums.get(index);
nums.set(index, nums.get(index - 1));
nums.set(index - 1, temp);
index--;
}
}
public boolean find(int value) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int twoSum = nums.get(left) + nums.get(right);
if (twoSum < value) {
left++;
} else if (twoSum > value) {
right--;
} else {
return true;
}
}
return false;
}}
更多题解参考：
